Праволинейные грамматики

Регулярные (автоматные) грамматикиотносятся к наиболее простому типу грамматик. Различают регулярные грамматики с левосторонними продукциями вида

A → Bx или A → x,

и регулярные грамматики с правосторонними продукциями вида

A → xB, или A → x, где A, B Î N, x Î S^*.

Пусть грамматика G = (N, S, P, S) задается следующим образом:

 

N = {S, L}, S = {a, b, 0, 1},

P = {S→aL, S→bL, S→a, S→b,

L→aL, L→bL, L→0L, L→1L,

L→a, L→b, L→0, L→1}.

 

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

Конечные автоматы

 

Конечным автоматомназывается пятерка

A = (Q, S, d, q₀, F),

где Q = {q₀, q₂, …, q_n}– конечное множество состояний устройства управления;

S = {a₁, a₂, …, a_k} – конечный входной алфавит;

d – функция переходов, отображающая Q S во множество подмножеств множества Q;

q₀ – начальное состояние устройства управления;

F – множество заключительных состояний, причем F Í Q.

Конечный автомат можно представить себе следующим образом. На бесконечной ленте с ячейками записана входная цепочка символов aÎ S^*; управляющее устройство с читающей головкой движется слева направо и считывает символы с ленты. После перехода к новой ячейке, управляющее устройство попадает в новое состояние, определяемое функцией переходов. На рисунке изображен автомат в начальном состоянии, считывающий первый символ входной цепочки { a_s1, a_s2, …, a_sp}.

 

 

Конфигурацией конечного автомата называется пара (q, w), где q Î Q – состояние устройства управления, а w Î S^* – неиспользованная часть входной цепочки. Такт автомата определяется на конфигурациях. Например, если d(q ₁, a) содержит q ₂, то, выполнив такт, автомат перейдет от конфигурации (q ₁, a w) к конфигурации (q ₂, w). Используя бинарное отношение, обозначаемое символом ├, указанный выше такт можно записать следующим образом:

(q ₁, a w)├ (q ₂, w).

Это говорит о том, что если конечный автоматнаходится в состоянии q ₁и входная головка обозревает входной символ а, то автомат может делать такт, за который он переходит в состояние, q ₂и сдвигает головку на одну ячейку вправо.

 

Входная цепочка w допускается автоматом, если найдется последовательность тактов, переводящая автомат из начальной конфигурации (q₀, w) в заключительную (q_f, e), здесь q_f – некоторое заключительное состояние, e - пустая цепочка.

Конечный автомат называется детерминированным, если множество d(q, a) содержит не более одного состояния для любых q Î Q и a Î S. Если множество d(q, a) содержит более одного состояния, то автомат называется недетерминированным. Единственное отличие недетерминированного конечного автомата от детерминированного заключается в том, что значениями функции переходов являются не состояния, а множества состояний (или, в терминах команд, возможны различные команды с одинаковыми левыми частями). Это соответствует тому факту, что в диаграмме состояний из одной вершины может исходить несколько дуг с оди­наковой пометкой.

 

Рассмотрим конечный детерминированный автомат А 1, допускающий все цепочки из символов 0 и 1, которые начинаются и оканчиваются 1. А1=({p, q, r}, {0, 1}, d, p, {r}), где d задается следующей таблицей.

 

d
Состояние	Вход
p	-	{q}
q	{q}	{r}
r	{q}	{r}

 

Функцию переходов d можно задать с помощью диаграммы.

 

Функцию переходов d можно задать с помощью команд:

d(p, 1) = q; d(q, 0) = q; d(q, 1) = r; d(r, 0) = q; d(r, 1) = r.

Для входа 1001 единственно возможной последовательностью конфигураций, начинающейся конфигурацией (p, 1001), будет

(p, 1001) ├ (q, 001)

├ (q, 01)

├ (q, 1)

├ (r, e)

Таким образом 1001 допускается автоматом А 1.

Рассмотрим конечный недетерминированный автомат А2, допускающий все цепочки из символов 0 и 1, которые оканчиваются цепочкой 010. А1=({s1, s2, s3, s4}, {0, 1}, d, s1, {s4}), где d задается следующей диаграммой.

 

 

d
Состояние	Вход
s1	{s1, s2}	{s1}
s2	-	{s3}
s3	{s4}	-
s4	-	-

 

Функцию переходов d можно задать с помощью таблицы.

 

 

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

Рассмотрим теперь произвольную автоматную грамматику G = (N, S, P, S) с правосторонними продукциями:

C → xB, или C → x, где C, B Î N, x ÎS *.

Построим для нее недетерминированный конечный автомат

A = (Q, S, d, q ₀, F),

где алфавиты S в грамматике и автомате совпадают; Q = N È{ D }, причем символ D не должен содер­жаться в N, q ₀ = S, F ={ D }, а d определяется следующим образом:

1) каждой продукции вида C → x ставится в соответствие команда d(C, x) = D;

2) каждой продукции вида C → xB ставится в соответствие команда d(C, x) = B;

3) других команд нет.

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

Пример. Пусть грамматика G = (N, S, P, S) задается следующим образом:

N = {S, L}, S = {a, b, 0, 1},

P = {S→aL, S→bL, S→a, S→b, L→aL, L→bL,

L→0L, L→1L, L→a, L→b, L→0, L→1}.

Построим для нее конечный автомат

A = (Q, S, d, q ₀, F),

 

S = {a, b, 0, 1}, Q = {S, L} È{ D }, q ₀ = S, F ={ D },

d(S, a) = L; d(S, b) = L; d(S, a) = D; d(S, b) = D; d(L, a) = L; d(L, b) = L;

d(L, 0) = L; d(L, 1) = L; d(L, a) = D; d(L, b) = D; d(L, 0) = D; d(L, 1) = D;

 

Теперь рассмотрим произвольный недетерминированный конеч­ный автомат

A = (Q, S, d, q ₀, F).

Такому автомату можно поставить в соответствие следующую автоматную грамматику:

G = (N, S, P, S),

где алфавиты S в грамматике и автомате совпадают; N = Q, S = q ₀, а множество Р строится следую­щим образом:

1) каждой команде автомата (q_i, a_j) = q_k ставится в соответствие продукция q_i → a_jq_k, если q _i, q_k Î Q, a_j ÎS;

2) каждой команде (q_i, a_j) = q_k ставится в соответствие еще одна продукция q_i → a_j, если q_k Î F;

3) других продукций нет.

 

Рассмотрим конечный детерминированный автомат А 1, допускающий все цепочки из символов 0 и 1, которые начинаются и оканчиваются 1. А1=({p, q, r}, {0, 1}, d, p, {r}), где d задается следующими командами:

d(p, 1) = q; d(q, 0) = q; d(q, 1) = r; d(r, 0) = q; d(r, 1) = r;

этому автомату поставим в соответствие следующую автоматную грамматику

G = (N, S, P, S),

S ={0, 1}, N ={p, q, r}, S = p,

P = {p→ 1q; q→ 0q; q→ 1r; q→ 1; r→ 0q; r→ 1r; r→ 1 }