[04.04.11] Лекция №9 (Конспекты - Теория формальных языков)

Лекция №9 [04.04.11]

Пример применения леммы о разрастании:

- КС-язык, ,

, , ,

,

выберем такое, что (это ключевой момент, количество букв достаточно большое, чтобы не рассматривать перекрёстные связи).

1) состоит только из букв - при попытке рассмотреть слова количество букв будет расти, а и останется тем же, а так нельзя;

2) состоит только из букв - тут то же самое;

3) состоит только из букв - тут то же самое;

4) состоит только из букв и (строго без ) – почти то же самое;

5) состоит только из букв и (строго без ) – да, то же;

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

Ещё пример:

пусть слово достаточно длинное: и

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

А возьмём , где состоит из , ,

нарушает условие

И значит, данный язык не является контекстно-свободным.

Теорема: если - КС-язык, а - регулярный язык, то - КС-язык.

Магазинные автоматы

- входной алфавит;

- магазинный алфавит;

- стартовое состояние;

- множество заключительных состояний;

- начальный магазинный символ (находится в магазине при старте работы автомата);

Команда МП-автомата (с магазинной памятью): , где

- текущее состояние блока управления;
- некоторый символ входного алфавита, записанный в той ячейке, которую в данный момент обозревает считывающая головка. Может быть пустым, , тогда выполняется независимо от того, какой символ находится на входной ленте;

- верхний символ магазина. Если магазин пуст ( ), то автомат работу заканчивает и ни одна из команд не применима к автомату с пустым магазином;

- новое состояние БУ;

- цепочка символов магазинного алфавита (в том числе и пустая), которая помещается в магазин вместо символа ;

Автомат с магазинной памятью задаётся упорядоченной семёркой:

, где

- множество состояний автомата;

- входной алфавит;

- магазинный алфавит;

- стартовое состояние;

- множество заключительных состояний;

- стартовый магазинный символ;

- множество команд МП-автомата;

Пример:

команды:

1)

2)

3) - если в , на ленте , в стеке , то переходим в и стираем в стеке;

4)

5)

Конфигурация МП-автомата - упорядоченная тройка , где - из множества состояний автомата, - входная цепочка, - магазинная цепочка.

Пусть - текущая конфигурация.

называют непосредственно выводимой из конфигурации , если в множестве команд МП-автомата есть команда

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

Любую конфигурацию называют начальной.

А любую называют заключительной.

Вывод на множестве конфигураций МП-автомата – последовательность (конечная или бесконечная), , .

Если - последняя конфигурация выводов, то - длина.

Допустимая цепочка МП-автомата – цепочка , на множестве конфигураций автомата существует вывод, связывающий начальную конфигурацию автомата с заключительной конфигурацией .

Язык, допускаемый МП-автоматом – это множество всех его допустимых цепочек.

Пример к тем рисованиям: