Studopediya

КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Графично представяне на нормален алгоритъм





където: PB аз - влизане за преобразуване; ОП аз - оператора на смяна.

Преобразуватели събития са свързани последователно в съответствие с правилата за номериране на схемата.

Пример за изготвяне на САЩ (символ пренареждане).

За да се намали състава на проблем ще използваме следните конвенции:

- В писмо P ще се обозначи въвеждане на думата;

- Буквата А ще бъде обозначен с думата азбука вход, т.е. набор от тези знаци, че и само, че могат да бъдат включени във входната дума Р (но в процеса на изпълнение на САЩ и други символи, може да се появи в обработените думите).

Проблем: A = {A, B}. Конвертиране дума P, така че в началото се оказа всички герои, а и в крайна сметка - всички символи б.

Например: babba → aabbb

Solution.

Тя ще изглежда, че за тази нужда задача сложно САЩ. Все пак, това не е така, проблемът се решава чрез WE съдържащ само един формула:

{Ба → аб

Докато в P дума отдясно на поне един символ на символ В е, тази формула ще бъде носене отляво на тази б. Формула спира да работи, когато правото на б а Не, това означава, че всички са от ляво на б.

Например:

babba → abbba → abbab → ababb → aabbb

Алгоритъмът се спря на последната дума, защото тя вече не е приложим за нашата формула.

Американският лесно реализирана пермутация, поставете и изтриване на символи. Въпреки това, в САЩ има и друг проблем: как да се определи характера (subword), за да бъдат обработени? Нека разгледаме този проблем в следния пример.

Пример за подготовка на САЩ (използване на специални символи).

Проблем: A = {A, B}. Махни от непразни дума P първия си характер. Празният думата не се променя.

Solution.

Ясно е, че премахването на първия знак на думата, трябва незабавно да се спре. Затова, изглежда, трябва да се реши проблема:

а (1)

б (2)

Все пак, това е грешен алгоритъм, какво може да се провери чрез прилагане на това думата bbaba:

бб а ба bbba

Както можете да видите, САЩ премахна характер не е първата дума и първата поява на човешкия характер, и това е различни неща. Този алгоритъм ще работи правилно, само ако на входа думата започва с. Ясно е, че формулите пермутация в САЩ няма да помогнат, защото След това тя ще, напротив, не работят на думи, започващи с.

Какво да се прави? Ние трябва по някакъв начин да определи, за да отбележи първия знак на думата, например, чрез поставяне пред него знак, казват *, различен от азбуката героите на една дума. След това, можете да използвате формулите на форма * лири за замяна на знака и първия знак на £ думата на празен и да се спре:

bbaba → * bbaba баба



И как да се сложи * преди първия знак? Тази формула се прилага → * с празната страна на лявата ръка, която по дефиниция, атрибути част от правото си на ляво от пътя.

Общо US получаваме следното:

→ * (1)

* (2),

* Б (3)

Проверете го в един и същи вход дума:

bbaba → * bbaba → ** bbaba → *** bbaba → ...

Както може да се види, този алгоритъм непрекъснато приписва левия зъбно колело. Защо?

Припомнете си, че изявлението на формулата с празна лявата част винаги се прилага, така че нашата формула (1) ще работи за неопределено време, блокиране на достъпа до други формули. Това предполага много важно правило: ако има формула в САЩ с празна лявата страна (→ β), а след това на мястото му - само в края на нас.

Ние отчитаме това правило и да пренапише нашата САЩ:

* А (1)

* Б (2)

→ * (3)

Ние се провери този алгоритъм:

bbaba → * bbaba баба

Тя ще изглежда, че всичко е в ред. Все пак, това не е така: нашият алгоритъм воля контура на празен вход думата, защото формула ще се прилага постоянно (3), и в съответствие с условията на проблема в САЩ тази дума трябва да спрат. Каква е причината за тази грешка? Фактът, че ние въведохме * знак за отбелязване на първия знак на думата, и след това да унищожи * и този символ. Но празни думи никой характер, така формула (1) и (2) никога няма да работи и с формула (3) се извършва непрекъснато. Ето защо, за да се вземат предвид случаите на празен вход дума, е необходимо след формулите (1) и (2) да напише още една формула, която унищожава "самотен" звездичката и да се спре на алгоритъма:

* А (1)

* Б (2)

* (3)

→ * (4)

Сега най-накрая стигна до правилния алгоритъм.

1.2 машина Тюринг

Той бе предложен от английски математик Тюринг в края на 30-те години на миналия век.

Фигура 5.1 - Машината на Тюринг

Тюринг информация машина включва лента за четене и писане на главата и управляващо устройство (фиг. 5.1).

Информация за дължина на безкрайна лента е последователност от клетки, всяка от които е записан точно само едно от множеството символ азбука V Т = {1, 2 ... A N}. Последователността на символи върху лентата образува дума = (1, 2, ... а |). Интервал между думите е също символ на набор V T. Например, # Аз V т.

От гледна точка на формалните граматики са много символи на азбуката V Т е набор от терминални символи.

Feed информация служи като външна памет на машината на Тюринг.

За четене - главата на запис е с изглед към една информация клетка лента, предава информация за съдържанието му към контролера, и в посока на последната запазва или променя съдържанието на клетката.

Устройството за управление е механизъм, който, при всяка стъпка в изчислението е набор от състояния Q = {Q 1, Q 2, ... р м}. В зависимост от р Аз състояние и й смята за символ на контролния блок генерира команда за изтриване или напишете желания символ в разгледа клетката, устройството за контрол преведени на ново състояние и движението на главата на съседна клетка информацията на лентата на. Концепцията за "държавен" формира "паметта на машината на Тюринг", т.е. предвид всички междинни състояния на, които са довели до сегашното състояние на Аз, машина р. Поради това, множеството от състояния на устройството за управление се нарича вътрешна памет от една машина на Тюринг. От гледна точка на формалните граматики, определени от символи на устройството за управление е набор от състояния на не-терминални символи. Сред всички страни от блока за управление трябва да бъдат разпределени р о - начално състояние ( "Старт") и р к - крайното състояние ( "Стоп"), което ще улесни формализирането на протоколи Машина на Тюринг и техния състав.

За да се формализира движенията на главата по отношение на информацията, ще се въведе допълнителна лента азбука D = {R, L, C}, където P - се отнася до движението на главата в дясно от информация лента за една клетка, L - наляво, една клетка и C - спрете.

Работата на машината на Тюринг е кратно повторение на следващия цикъл на елементарни действия:

1) четене на характера на й, който е под главата за четене;

2) Екипът на търсене, който да отговаря на сегашното състояние на контролната единица р аз, и се смята за символ на й, т.е.

р к а к => Q | а м D;

3) представяне на екипа намерено, т.е. Влизане изследва клетъчен символ м, устройство за контрол на преведен на държавен р аз и движението на главата на съседния информация клетка лентата D.

Тези три стъпки са елементарната стъпка от алгоритмичен процес.

Последователността на команди за изпълнение на процеса на изчисляване генерира Тюринг протокол машина или програма алгоритмичен процес.

Трябва да се отбележи, че няма две инструкции не могат да бъдат от същата двойка от текущото състояние Q I и четене символ й, т.е. (Q и на J). Тюринг машина спира, само ако в следващата стъпка, управляващото устройство генерира състояние р к Резултатът от машината на Тюринг е последната дума на кинопреглед.

Математически модел на машина на Тюринг е:

T = <V т; Q; D; й; Y; х>,

където: V T = {а аз; 2; ... А п} - Външни символи на паметта;
Q = {р о, р аз ; Q 2; ... Q m} - Вътрешната памет на героите;
D = {P; А; C} - Символи на движение на главата;
J: Q А У Т => V т - Функция на изхода на една машина на Тюринг;
Y: Q А У Т => Q - Функцията за преход от една машина на Тюринг.
х: Q А У Т => D - Функция за преместване на главата на машината на Тюринг.

Описание на Тюринг машина се определя от написването всички думи в кинопреглед, позицията на главата спрямо информацията на лента клетка и текущото състояние на устройството за управление. Такова описание се нарича конфигурация машина Тюринг:

К = I воден б,

където - дума, от лявата страна на главата;

б - дума за правото на главата;

р аз - текущото състояние на машината на Тюринг.

В аз", който се намира в клетката под четящата глава, първия знак на думата б, т.е. В = (а й д).

За не-финалната конфигурация може да се прилага само един отбор, който поставя на машината в нова конфигурация. Така че изпълнява дискретна и детерминизъм на алгоритмичен процес.

За улеснение на анализ на изчислителни алгоритми Post математик предложи да се ограничи набор от външни азбука V Т два знака, т.е. V Т = {|; #}, Където "|" (Wand) е символ на едноместно кода, и "#" (диез или паунд) са с интервал между цифрите. Въпреки това, всяко положително число може да бъде представена от информация за последователността на лентата пръчки, както е показано в таблица. 5.1.

Таблица 5.1

Броят на десетичната система "Словото" в едноместно код на информацията на лента
| 1 = включено
|| = 1 1 + 1
1 = 2 + 1
аз ... | = 1, I + 1

За информация за поръчка компилация лента протоколи граница само в една посока, т.е.. Д., има ляво и дясно polulenty. В зависимост от различни конфигурации, взети схемата запис polulenty на машина на Тюринг (таб. 5.2).

Таблица 5.2

стандарт Информация polulenta
конфигурация прав отляво
първичен р п | х 1 1 + # | х 2 + 1 # ... # | х п + 1 | х 1 1 + # | х 2 + 1 # ... # | Xn р н |
Последна дума р к | Y + 1 | у р к |

Работата на машината на Тюринг е удобно на масата за протокол и графиката.

В протокола всички команди трябва да бъдат написани на един подреден списък. Последната стъпка е да бъде стойност, получена от предварително определена функция, т.е.. Е. Y = F (X 1, X 2, ... X п).

Например,

1) р п а аз -> р аз на к D;

2) р аз к -> р к а аз Г;

.................................

п) Q | а м -> р к а н C.

Когато таблица, описваща всяка линия има името на текущото състояние на машината, както и символът външна памет колона-име. След това елементите на таблицата са в дясната част на отбора (Q J а аз D) на.

Таблица 5.3

ток Символи о т
състояние и аз и ... м
р п Q и J на D ...
р аз ... р к а аз D ...
... ... ... ... ...
р аз ... ... ... р к а н C

таблична форма за описване на машината е по-компактен и ви позволява да използвате методите матрица за анализ за структурата на алгоритъм за оптимизация.

На Графика представителства на върховете на графиката са състоянието на машината на Тюринг, и дъги - преходи в тези държави, които са осигурени от екипа. В една и съща точка на дъгата на знакови за четене / писане герои в наблюдавания клетката и да се премести на командата главата (Фиг. 5.2). Граф Тюринг машина, която изпълнява определен алгоритъм, често по-нататък графика-схема на алгоритъм (GSA).

Фигура 5.2 - Graph диаграма машина Тюринг

Пример 1 от машината на Тюринг. T 2 = основната функция на п = 1 на десния polulente:

T 2: р о | х + 1 # ®q к || #;

Протокол T 2. 1) р на | ®q # 1 R; 2) Q 1 | ®q # 1 R; 3) Q 1 # 2 # ®q | L; 4) Q 2 # ®q к | C. ток Символи о т
състояние #
Q на Q 1 P # -
Q 1 Q 1 P # Q 2 | A
Q 2 - Q 1 | C

Фигура 5.3 - Графиката на функцията на основата алгоритъм N = 1

Пример 2 Машина на Тюринг. T 4 = основна функция I M, N с дясното polulente:

T 4: р о | 1 1 x1 + # | 2 х 2 + 1 # # ... | М + 1 XM # # ... | N Xn + 1 # ®q к | XM + 1 #

когато | аз - Думата на позицията информация лента-тото,

| XI + 1 - броят на "пръчки".

За да намерите информация за лента -тото дума, задаване на тезгяха | м, което показва мястото на думата | м XM + 1 в думата последователност.

T 4: р о | м # | 1 1 x1 + # | 2 х 2 + 1 # # ... | М + 1 XM # | N Xn + 1 ® р к | М + 1 XM.

ток Символи о т
състояние | # )
р о Q 1 P # - -
Q 1 Q 1 | G Q 2) P -
Q 2 Q 2 # P Q 3) L -
Q 3 - Q A # 3 Q 4)
Q 4 Q 4 | A Q # 5 P -
Q 5 Q # 6 P - Q 8 P #
Q 6 Q 6 | P - Q 7) P
Q 7 - Q P 7 # Q 2 # P
р 8 - Q 8 P # Q R 9 #
Q 9 Q 9 | P Q # 10 P -
Q 10 Q # 10 P Q # 11 P -
Q 11 Q # 10 P Q # 12 A -
Q 12 Q 13 | A Q # 12 A -
Q 13 Q 13 | A Q # 14 P -
Q 14 р к | C - -

Фиг. 5.4 показва графика, който реализира основната функция I M, N.

Това ще позволи на всеки да премине към правото, маркиране на един символ в думата | м, за да изтриете следващата дума | М-1 предходната | М + 1 XI.

За да се организира такава функция за изчисление, трябва да се увеличи броят на външна азбука памет, което ще доведе до намаляване на броя на състояния на устройството за управление и за рационализиране на целия процес на изчисляване.

Нека V т = {|, #, (} . Главата за четене е в рамките на първия знак на думата брояч | м.

първия знак на думата се заличава Когато "начало" команда | м, и на главата започва да се движи надясно.

След прочитането на всички герои от дума | м р 1 отбор # ®q 2) P постави скобата, обхващаща останалите думи на героите | м, а главата се премества на пода | X1 + 1.

В командния Q 2 | ®q 2 # P изтрива всичките думи на героите | 1 x1 + 1 и сложи на затваряне скоба р 2 # ®q 3) A. Тя започва преместването на главата за четене на ляво за следващата дума характер | М-2.

Фигура 5.4 - граф основните функции I M, N

Така организираната цикъл. След това, контролерът изтрива втората дума, третият, и така нататък, докато има герои .. "|" В тезгяха.

След изтриване на всички герои в брояча на р стъпка 5) ®q 8 # P глава затрива затваряне скоба, минава през всички пропуски "#", командния Q 8) ®q 9 # P определя мястото на думата | м XM + 1, минава през всичките думи на героите | м XM + 1 и продължава да пази всичките думи още от думата | м XM + 1 до р 10 отбора | ®q 10 # P и Q 11 | ®q 10 # п. Когато четете лента в съседни клетки са знаците "#", то в края и главата обратно към първия знак на думата | м XM + 1 тип: р ®Q 11 # 12 # A, Q ®Q 12 # 12 # A, Q 12 | ®Q 13 | R, Q 13 | ®Q 13 | R, Q ®Q 13 # 14 # P и Q 14 | ®q к | C.

Пример 3 Тюринг машина. T 6 м до веднъж дума | х + 1 от дясната polulente:

Т 6: Q O | X + 1 # ® р к | 1 х 1 # | 2 х + 1 # .. # | м х + # 1.

За да се извърши м копия, трябва да въведете информацията за брояча. Т.е. промяна на първоначалната конфигурация на машината, който определя броя на копията | м:

Т 6: Q O | м # | # Х + 1 ® р к | 1 х 1 # | 2 х + 1 # .. # | м х + # 1.

Всяка дума в правото на подаване | м премахва един знак, след което се извършва обичайните копиране думите | х + 1, маркировка всеки отбор извършва символ Q 2 | ®q 3 (P и затваряне дума | х + 1 отбор Q 3 # ®q 4 (P. След прехвърлянето на всички герои на една дума | х 1 глава се връща към най-левия характер на думата | м и го изтрива.

. Нека V т = {|, #, (, )}.

ток Символи о т
състояние | # ( )
Q на Q 1 P # - - Q 8 P #
Q 1 Q 1 | G Q 2) P - Q 2) P
Q 2 Q 3 - Q 2) P Q 2) P
Q 3 Q 3 | P Q 4) P - Q 4) P
Q 4 Q 4 | P Q 5 | A - -
Q 5 Q 5 | A - 6, Q (N Q 5)
Q 6 Q 3 - - Q 7) L
Q 7 Q 7 | A Q P 7 # Q 7 (A Q 7) L
р 8 Q 9 | A - Q 8 (P Q 8) P
Q 9 р к | C Q R 9 # Q 9 | A Q 9 # A

Фигура 5.5 - граф думи репликация алгоритъм | х + 1

Процесът продължава, докато, докато не извадите всички герои в словото на 1 m. След това премахнете всички поддържащи герои "(" и ")", и сложи главата на машината в началото на първата дума | X + 1. Много отбори са представени маса и работна машина е показан на графиката на фиг. 5.5.


2 Примери за задачи

1. Изчисляването на продукта от две числа в унарна код.

2. Изберете модела на Тюринг машина за изпълнение на основни комунални услуги и основни функции.

р п | х # | Y # | Z # | S # | т Þ р к | (Y ¸ Z) # | (X + T)

За всяка машина Тюринг да направи таблица на поведение и да изготви графика. Изрязан изваждане "за извършване на х> у> Z> а> т и х <у <Z <S <т.

3 Setting

За избран в съответствие с целите за тази задача (две части):

1) Разработване на протокол Марков нормално алгоритъм.

2) Разработване на графика диаграма Марков нормално алгоритъм.

3) Debug протокол емулатор Марков машина.

4) Разработване на маса преход протокол и графика на металорежещи членки на Тюринг с десния polulentoy.

5) Debug протокол емулатор машина Тюринг.

6) Направете изводи.

4 Съдържание на доклада

1) Условия, задачи в съответствие с изпълнение.

2) Определяне на "Normal Марков алгоритъм."

3) Протокол Марков нормално алгоритъм за решаване на проблема.

4) Count диаграма Марков нормално алгоритъм за решаване на проблема.

5) Математическият модел на машина на Тюринг.

6) Доклад на машината на Тюринг, която решава проблема.

7) таблица на преходите от една машина на Тюринг, която решава проблема.

8) Държавна графика Тюринг машина, която решава проблема.

9) Резултатите от отстраняване на грешки на Тюринг машина за емулатор.

10) Анализ на резултатите и изводите.

5 заведения за работни места

По-долу са дадени варианти работа, състояща се от две части. Първата част - на състоянието на проблема, който трябва да бъде решен Марков нормално алгоритъм. Втората част - състоянието на проблема, трябва да бъде решен от машина Тюринг.

В първата част на тази работа.

1. = {F, Н, р}. Думата The P да замени всички двойки рН на л.

2. = {F, Н, р}. С една дума Р Е се заменя само с първата двойка на рН, ако има такъв.

3. = {А, В, С}. Присвояване на думата вляво от пътя БКК П.

4. = {А, В, С}. Замяна на думата P е празна дума, т.е. премахнете от P всички герои.

5. = {А, В, С}. Замяна на всеки вход дума на дума с.

6. Запис на нормалната алгоритъм, който не променя вход думата (във всеки азбука A).

7. = {А, В, С}. За да се определи дали даден знак е част от P дума. Отговор (изходящ): думата на един, ако е включен, или една празна дума, ако не е включено.

8. A = {A, B} . Ако думата P навлиза в повече знаци, символи, отколкото б, в отговор на издаване на думата на един символ, ако има редица P равен и б, въпросът в отговор на празна дума, но иначе се даде отговор б.

9. = {0,1,2,3}. Конвертиране дума P, така че първите са всички четни числа (0 и 2), а след това - всичко странно.

10. = {А, В, С}. Конвертиране дума P така, че за първи път са всички герои, а след това - всички герои В, и в крайна сметка - всички герои в.

11. = {А, В, С}. За да се определи колко различни символи на една дума, съставена от P; получите отговор в единна система за номериране (например: acaac → | |).

12. = {А, В, С}. В не-празна дума за удвояване на първия символ на P, т.е. да се припише, че символ вляво от P.

13. = {А, В, С}. За първи символ на не-празна дума P, за да вмъкнете символ век.

14. = {А, В, С}. От думите на P, за да се отстрани втория знак, ако има такъв.

15. = {А, В, С}. Ако думата P не е по-малко от два символа, първите два знака да се пренаредят.

16. А = {0,1,2}. Като се има предвид непразни дума P запис трикомпонентна номер, изтриване на запис на всички нули.

17. = {А, В, С}. Присвояване на правилната дума за думата ABC П.

18. = {А, В, С}. Махни от непразни дума P своя окончателен характер.

19. = {А, В, С}. Удвояването на всеки знак в думата P (например: БАКБ → bbaaccbb).

20. A = {A, B} . Присвояване на правото на думата P стърчи толкова, колкото всички символи, включени в P (например: Babb → Babb |).

21. A = {A, B} . Присвояване на правото на думата P като пръчки, с колко много последователни символи започва една дума (например: aababa → aababa | |).

22. = {А, В, С}. Махни от думите на втората поява на символ П а за това, ако има такава.

23. А = {А, В, С}. Махни от думите на третата поява на характер P А, ако има такъв.

24. А = {А, В, С}. Оставете в P дума, само първата поява на човешкия характер, ако има такъв.

25. = {А, В, С}. В не-празна дума P да напусне само последния символ.

26. = {А, В, С}. От всички герои в една дума срещания P остави само на последния запис, ако има такъв.

27. А = {А, В, С}. P Ако думата започва с, след това замени Р е празна дума, но иначе P не се променя.

28. A = {A, B} . Ако думата P съдържа както герои а и б, след това замени P е празна дума.

29. А = {А, В, С}. Ако буквите в една не-празна дума P не е подреден по азбучен ред, замени р е празна дума, но в противен случай P не се променя.

30. А = {А, В, С}. Ако P е различна от тази дума, абака, след това да го замени с една празна дума.

31. А = {А, В, С}. За да се определи дали първият знак влиза не-празна дума P отново в думата. Отговор: Думата на, ако е включен, или една празна дума по различен начин.

32. A = {A, B} . Преместете първия знак на не-празна дума P в края на думата.

33. A = {A, B} . Трансфер последния знак на непразни дума P в началото на думата.

34. A = {A, B} . В не-празна дума P пренареждане на първите и последните героите.

35. A = {A, B} . Ако не е празна дума P съответства на първите и последните символи, след това изтрийте и двете от тези символи, иначе думата не се променя.

36. A = {A, B} . Определя дали P дума палиндром на (Changeling, симетрична дума). Отговор: Думата на, ако е така, или иначе празна дума.

37. A = {A, B} . Нека думата P има нечетен дължина. Извадете го от средната символ.

38. А = {(,)}. Определете дали дума Р е базирана на скоби.

Отговор: D (да) или N (не)

39.A = {A, B}. Включете дума P (например: ABB → BBA).

Втората част от работата.

1. = {А, В, С}. Присвояване на ляво към P символ дума Б (P → BP).

2. = {А, В, С}. Присвояване на правото на ж.к. думата P символи (P → РВС).

3. = {А, В, С}. Замяна с втори характер във всяка дума П.

4. = {А, В, С}. Оставете в P дума само първия знак (не на празна дума

промените).

5. = {А, В, С}. Оставете в P дума само миналата характер (празната дума не се променя).

6. = {А, В, С}. Определете дали думата P AB. Отговор (изходящ): дума аб, ако е така, или иначе празна дума.

7. = {А, В, С}. За да се определи дали думата символ П а на. Отговор: Думата от един символ на (да, включени в комплекта) или празна дума (не).

8. = {А, В, С}. Ако думата не включва символ P A, P, за да замени всички символи б за в, или в отговор на въпрос на един символ дума.

9. = {А, В, С}. Присвояване на ляво към не-празна дума P първия си характер.

10. A = {A, B} . За непразни дума P да се определи дали част от него отново го първия знак. Отговор: а (да) или празна дума.

11. A = {A, B} . В не-празна дума P, за да сменяте първите и последните си герои.

12. A = {A, B} . Определя P палиндром (Changeling, симетрична дума) или не. Отговор: а (да) или празна дума.

13. A = {A, B} . Замяна на всяка поява на P на бб.

14. = {А, В, С}. Замяна на всяка поява на P в аб в.

15. A = {A, B} . Удвои дума Р (например: ABB → abbabb).

16. A = {A, B} . Удвоява на всеки характер на думата P (например: Bab → bbaabb).

17. A = {A, B} . Включете дума P (например: ABB → BBA).

6 Референции

1) Pil'shchikov VN Абрамов VG Vylitok AA Hot IV Тюринг машина и Марков алгоритми. Разрешаване на проблеми. (Training Toolkit) - M:. Московския държавен университет, 2006 г. - 47 стр.

2) VF Пономарьов Дискретна математика за inzhenerov.- Калининград: KSTU FSEIHPE, 2010.- 351 стр.






; Дата: 10.31.2014; ; Прегледи: 992; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:





zdes-stroika.ru - Studopediya (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 66.102.9.24
Page генерирана за: 0.098 сек.