На этой странице представлены исправленные упражнения на теория языка, точнее на автоматах на батарейках.
Упражнение 1
То грамматика (линейный) S → aSb | ε порождает язык {aнетбнет : n ≥ 0}. Вдохновленный этим примером, предложите грамматики для каждого из следующих языков: {a2н(до н.э)3н : n ≥ 0}, {а2нб3против20н : n ≥ 0}, {а2нб3нпротив20 : n ≥ 0}, {амбнет : м ≥ п ≥ 0}
1 – S → aaSbcbcbc | ε
2 – S → aaSc20 | ббб
3 – С → Хс20; Х → ааХbbb | ε
4 – С → аС | асб | ε
Упражнение 2
Какой язык порождается следующей грамматикой:
С → аСа | аБа
Б → ББ | б
дайавтомат на батарейках порожденный следующим языком: L(G) ={aнетбмпротивмd2н | 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 
FR 
EN 
ES