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

Способы задания конечных автоматов

Определение конечного автомата как пятерки объектов с детальным описанием функции переходов слишком громоздко и неинформативно.

Существуют два более удобных способа описания автоматов:

1. таблица переходов

2. диаграмма (граф) переходов

Таблица переходов: строки отмечены состояниями, а столбцы - входными символами. Начальное состояние находится всегда в первой строке, в конечные состояния – отмечены символом *.

Составим таблицу переходов КА из примера 1.

	a	b
q0	{q1}	{q0}
q1	{q1}	{q2}
q2	{q3}	{q0}
q3^*	{q3}	{q3}

Диаграммой переходов НКА называется неупорядоченный граф, удовлетворяющий следующим условиям:

§ каждому состоянию q соответствует некоторая вершина, отмеченная его именем;

§ диаграмма переходов содержит дугу из состояния p в состояние q, отмеченную символом a, если р Î d (q, a). Если существуют несколько входных символов, переводящих автомат из состояния p в состояние q, то диаграмма переходов может содержать дугу, отмеченную списком этих символов

§ вершины, соответствующие заключительным состояниям, отмечаются двойным кружком, остальные состояния – одинарным.

На рисунке приведен граф переходов конечного автомата из примера 1:

a

b

a

a, b

b

b

a

К классу контекстно-свободных грамматик (КС) относятся грамматики, у которых не накладывается никаких ограничений на вид правых частей их правил, а левая часть каждого правила – единственный нетерминал. С помощью КС-грамматик задаются синтаксис языков программирования.

Напомним, что все правила КС-грамматики имеют вид: А®a, где А Î N, a Î ТÈN. КС-грамматики служат для определения КС-языков и их регулярных подмножеств.

Дата добавления: 2014-01-03