На этой странице представлены исправленные упражнения на теория языка, точнее на автоматах на батарейках.

Упражнение 1

То грамматика (линейный) S → aSb | ε порождает язык {aнетбнет : n ≥ 0}. Вдохновленный этим примером, предложите грамматики для каждого из следующих языков: {a(до н.э) : n ≥ 0}, {аб3против20н : n ≥ 0}, {абпротив20 : n ≥ 0}, {амбнет : м ≥ п ≥ 0}

1 – S → aaSbcbcbc | ε

2 – S → aaSc20 | ббб

3 – С → Хс20; Х → ааХbbb | ε

4 – С → аС | асб | ε

Упражнение 2

Какой язык порождается следующей грамматикой:

С → аСа | аБа

Б → ББ | б

дайавтомат на батарейках порожденный следующим языком: L(G) ={aнетбмпротивмd | n≥0, m > 0}.

В грамматике первое правило рекурсивно генерирует столько букв a на каждом конце слова. Второе правило генерирует хотя бы одну b внутри слова. Таким образом, сгенерированный язык L(G) = {aнетбмвнет | п > 0, т > 0}.

Прежде чем строить автомат, вы должны сначала понять правила грамматики. Заметим, что крайние точки находятся в степени n, а центр — в степени m. Таким образом, язык может быть сгенерирован правилами типа A→aAa|B. Мы выводим два правила, порождающие язык S →aSdd | ИМЕЕТ ; А → bAc | до н.э

Упражнение 3

Возьмем автомат, производящий палиндром, то есть слова, которые читаются одинаково как в левом, так и в правом чтении. Тогда автомат:

исправлены упражнения по теории языков выталкивающих автоматов

Приведите таблицу переходов и все производные от слов ab и abb. Затем покажите удачным выводом, что слова аааа и бааб являются палиндромами.

исправлены упражнения по теории языков выталкивающих автоматов

Происхождение слова аб:

исправлены упражнения по теории языков выталкивающих автоматов

Происхождение слова абб:

исправлены упражнения по теории языков выталкивающих автоматов

Удачный вывод слов aaaa и baab:

исправлены упражнения по теории языков выталкивающих автоматов

Упражнение 4

Пусть алфавит A = {a, b} и язык L = {a*b}. Напишите грамматику этого языка. Найдите автомат на батарейках, который может читать этот язык.

G = {T = {a,b}, N = {S}, S = {S}, P = {S -> b, S -> aS}}

Здесь мы замечаем, что стек бесполезен, нулевое использование стека равносильно использованию пустой буквы.

исправлены упражнения по теории языков выталкивающих автоматов

С лямбдой пустая буква.

Упражнение 5

Пусть алфавит A = {a, b} и язык L = {aнет бп /n >= 0 и n <= p <= 2n }. Напишите грамматику этого языка и покажите, что это алгебраический язык. Найдите автомат на батарейках, который может читать этот язык.

G = {T = {a,b}, N = {S}, S = S, P = {S -> ε | асб | асбб }}

Мы также можем написать грамматику следующим образом

Обратите внимание, что правила учитывают формат грамматик типа 2. Однако эта грамматика не учитывает формат типа 3.

исправлены упражнения по теории языков выталкивающих автоматов

Z — это символ, который помещается в стек при инициализации (символ конца стека).

Упражнение 6

Напишите алгебраическую грамматику, которая может написать любое регулярное выражение с алфавитом {0,1}. Для информации, алгебраическая грамматика содержит алфавит {0,1,(,), ∪,*, ∅, ε}. Проверка регулярного выражения (0 ∪ (10)*1)*

Давайте рассмотрим правила формирования регулярного выражения:

0 или 1 отдельно: S→0 | 1

Стоп-слово или эпсилон: S→∅ | ε

Союз двух подслов: S→S ∪ S

Конкатенация двух подслов: S→ SS

Звезда подслова: S→S*

Брекетинг приоритета: S→(S)

Взяв слово, мы получим следующие производные:

исправлены упражнения по теории языков выталкивающих автоматов

Это дает следующее дерево вывода:

исправлены упражнения по теории языков выталкивающих автоматов

Делиться
ru_RURU