Сборник задач по теории автоматов (стр. 3 )

2.  Задаём понятия (нетерминальные знаки), через которые можно выразить свойства строк языка:

- строка заданного языка,

- правильная строка с одним знаком .

3.  Сформулируем гипотезу, которая выражает свойства языка через заданные понятия:

Правильная строка языка есть последовательность знаков .

4.  Представим гипотезу в виде продукций грамматики , где . Тогда

5.  Проверим полученную грамматику на предмет порождения ею строк заданного языка

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

Проведём индукцию по длине вывода путём использования первой группы продукций грамматики. При длине вывода 1 и 2 получаем строки, принадлежащие заданному языку. Пусть получена строка языка при длине вывода : , , . И пусть строка может быть преобразована в правильную строку, тогда при длине вывода получим:

Если часть строки удовлетворяет свойствам языка, то и вся строка удовлетворяет свойствам языка.

Вывод: грамматика порождает заданный язык.

Задача 11

Задана формальная грамматика , где

a)  , ,

b)  , ,

Какой язык она порождает?

Задача 12

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

a)  язык, состоящий из строк алфавита таких, что число знаков в строке меньше, чем число знаков ;

b)  язык чисел в представлении с фиксированной точкой в десятичной системе счисления;

c)  язык целых чисел со знаком и без знака;

d)  язык, состоящий из строк алфавита таких, что число знаков в строке равно числу знаков .

Занятие 1.4. Контекстно-свободные грамматики

Задача 13

Контекстно-свободная грамматика (КС-грамматика) задана множеством продукций

Получить эквивалентную ей КС-грамматику без -продукций.

Решение

1.  Грамматика является КС-грамматикой, так как все её продукции имеют вид . Грамматика содержит -продукцию, например, .

2.  Применим процедуру эквивалентного преобразования грамматики в форму без -продукций:

a)  Пусть , , где . Тогда ,.

b)  Фиксируем -порождающую продукцию

c)  Добавляем в продукции из , в которых опущены -порождающие нетерминальные знаки : .

d)  Удаляем из зафиксированную продукцию и переносим из в новые -продукции, которые появились в на шаге c: , , .

e)  Повторяем шаги b, c, d пока :

-  фиксируем ;

-  ;

-  .

f)  Так как , то завершаем процедуру.

3.  Строим грамматику следующим образом: и содержат те терминальные и нетерминальные знаки, которые присутствуют в продукциях . Далее , а

Задача 14

КС-грамматика задана множеством продукций

Получить эквивалентную ей КС-грамматику без цепных продукций.

Решение

1.  Грамматика является КС-грамматикой, так как все её продукции имеют вид . Непосредственно видно, что грамматика содержит цепные продукции.

2.  Применим процедуру удаления цепных продукций.

a)  Пусть , , где - множество цепных продукций. Тогда . Пусть .