Мастихина А.А. Формальные языки и автоматы, для РК-6, страница 4

Получившийся автомат таков:b, 13?a, 1a, 0 ?K b, 0-b, 0∗1 a, 02Порождающая грамматика имеет видI → aI|bA, A → aI|bB, B → bB|aI|a|b.8Типовой расчет.Задача №1.По словесному описанию языка составить регулярное выражение.Составить грамматику, порождающую данный язык и выписать выводкакого-нибудь четырехбуквенного или пятибуквенного слова.1) Каждое слово языка содержит подслово abb или aac.2) Все слова языка имеют длину не менее 3 и не начинаются с буквы c.3) Длина каждого слова не меньше 2, и вторая буква всегда b.4) Перед каждой буквой c стоит a.5) Буква c может встречаться только как часть подслова acb.6) В каждом слове содержится не более двух букв c.7) Ни в одном слове буква b не следующая после c.8) Ни в одном слове нет двух и более букв a подряд.9) В словах языка нет ни подслова ba, ни подслова bb.10) После буквы a в слове языка всегда идет bc.11) Длина каждого слова не меньше 2, предпоследняя буква каждогослова - c.12) Ни одно слово не содержит подслова ab.13) Буква c не встречается ни в одном слове раньше («левее»), чем21встретится хотя бы одна буква a.14) На всех нечетных местах каждого слова находится a.15) Если слово начинается на ab, оно заканчивается на с.16) Если в слове есть буква a, то она написана не менее 2-х раз подряд.17) На четных местах каждого слова находится b, пустого слова нет.18) В словах языка после буквы a всегда идет bb.19) Перед каждой буквой c вседа стоит aa.20) Ни одно слово не содержит подслова cc.21) Если в слове есть буква b, то есть и a.22) Язык состоит из всех слов четной длины.23) В каждом слове 3 буквы c, одна из них в конце.24) Язык состоит из всех слов нечетной длины.25) Каждое слово содержит не менее 3-х букв a.26) Ни одно слово не содержит подслова cb.27) Буква b не встречается «правее» буквы a ни в одном слове.28) На четных местах каждого слова находится буква c.29) В каждом слове — не менее 4-х букв b.30) Все слова начинаются и заканчиваются на одну и ту же букву.Задание №2Поисточникуab-a ta ?1) ∗ -bbaab4) ∗t -7) ∗a-a-bt -a- ab-batсоставитьa2) ∗ -aрегулярноеbbt -b?ba5) ∗aat bba8) ∗-aat bвыражение.b-b3) ∗t -a-b-a?at6) ∗a-bbt -ata9) ∗t -a--bbbat-c10)∗-ab--abat?11)∗-a-b22t bt12)∗-a-a-bt∗ b-t-a -a13)∗t -bab--b?a14)∗ --at ab16)∗a--a-ac19)∗-a22)∗b--ab--bt ca-ct23)∗-a28)∗b-c-ac-cbtb?18)∗-a-a-a21)∗t -bttc ?26)∗at29)∗b t c - b?24)∗-b-b--ba 15)∗t -b--bbt ab20)∗t a-ba25)∗bta ?a17)∗ -a-c-bt -cabt aa-c-c?a -bt-b30)∗-caacca∗tbtt -aЗадание №31) По данной грамматике составить источник;2) детерминировать его;3) получить автомат, представляющий тот же язык, минимизировать полученный автомат;4) записать грамматику для минимального автомата.1) I → a|aA|aB, A → aA|b, B → aC|aA|bC, C → bC|b;2) I → aA|aB|bI, A → bB|Λ, B → aI|aC|a, C → a|bB|b;3) I → aA|aB|aC, A → aB|bA|bC, B → a|b, C → aC|bB|Λ;4) I → aA|b|Λ, A → aB|aC|bI, B → a|b, C → a|bB|b;5) I → aA|aB|bB, A → aA|bI|Λ, B → aC|bB, C → bB;6) I → aA|aB|a, A → a|bA, B → aC|bA|bC, C → bC|b;23?-bt -c-btc a27)∗b∗ -ab--att7) I → aI|bA|bB, A → aB|b, B → bI|bC|b, C → a|bB|b;8) I → aA|aB|aC, A → aA|aC|bB, B → a|b, C → aB|bB|bC;9) I → aB|bA|bB, A → aA|a|bI, B → aB|bC, C → aB|A;10) I → b|bA|bB, A → a|bA, B → aC|bA|bC, C → aC|a11) I → aI|bA|bB, A → aB|Λ, B → bI|bC|b, C → a|aB|b;12) I → bA|bB|bC, A → aA|aC|bB, B → a|b, C → aB|bC|Λ;13) I → a|bA|Λ, A → aI|bB|bC, B → a|bC, C → a|aB|b;14) I → aB|bB|bA, A → aI|bA|Λ, B → aB|bC, C → aB;15) I → bA|bB|b, A → aA|b, B → aA|aC|bC, C → aC|a;16) I → aA|aB|bI, A → a|bB, B → aI|aC|a, C → a|aB|b;17) I → bA|bB|bC, A → aB|bA|bC, B → a|b, C → aB|aC|bB;18) I → aB|aA|bB, A → aI|bA|b, B → aC|bB, C → bB|A;19) I → aA|aC|a, A → aB|aC|bB, B → bB|b, C → aC|b;20) I → aB|aC|bI, A → a|bC|b, B → bC|Λ, C → a|bC|b;21) I → aA|aB|aC, A → a|b, B → aB|bA|Λ, C → aA|bB|bC;22) I → aB|b|Λ, A → a|bC|b, B → aA|aC|bI, C → aA|b;23) I → aA|aC|bA, A → aB|bA, B → bA, C → aC|bI|Λ;24) I → aB|aC|a, A → bA|b, B → a|bB, C → aA|bA|bB;25) I → aI|bA|bC, A → bI|bB|b, B → a|bA|b, C → aA|b;26) I → aB|aC|aA, A → aC|bA|bC, B → aA|aB|bC, C → a|b;27) I → aA|bA|bC, A → aA|bB, B → aA|C, C → aC|a|bI;28) I → bA|bB|bC, A → a|b, B → bB|aA|Λ, C → bA|aB|aC;29) I → bA|bC|b, A → aB|bB|bC, B → aB|a, C → bC|a;30) I → bI|aA|aC, A → aI|aB|a, B → a|aA|b, C → bA|a.249Литература1.Ахо А., Ульман Дж.

Теория синтаксического анализа, перевода и компиляции: Пер. с англ. М.: Мир, 1978.2. Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: Изд-во МГТУ им. Н.Э.Баумана, 2001.3. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. М.: Наука, 1985.4. Трахтенброт Б.А., Бардзин Я.М. Конечные автоматы (поведение исинтез). М.: Наука, 197025Содержание1Предварительные сведения.22Регулярные языки.23Источники и языки.44Грамматики.85 Детерминированные источники.116Автоматы.137Минимизация автоматов.178 Типовой расчет.219 Литература2526.