Регулярные грамматики и конечные автоматы

Введение

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

В правой регулярной грамматике весь набор правила может быть в одном из следующих форматов:

• A → a
• A → aB
• A → ε

В левой регулярной грамматике весь набор правил может быть в одном из следующих форматов:

Статья: Регулярные грамматики и конечные автоматы

Найди решение своей задачи среди 1 000 000 ответов

Найти решение задачи

• A → a
• A → Ba
• A → ε

Здесь;

1. Большие буквы (A, B) призваны обозначить не терминалы из множества N.
2. Строчные буквы (a, b) служат для обозначения терминалов из множества Σ.
3. ε должен обозначать пустую строку, то есть строку, имеющую длину нуль.

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

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

Регулярные грамматики и конечные автоматы

Конечным автоматом является определённое устройство, которое обладает конечным числом состояний и предназначено для прочтения слов заданного конечного алфавита. По умолчанию считается, что слово занесено на некоторую ленту, составленную из ячеек, в каждую из которых занесена одна буква алфавита. Чтение ленты выполняется в дискретные такты времени в направлении слева направо. Подразумевается, что считывание произвольного слова «a» автомат должен начинать из специально заданного начального состояния. Считывание очередного символа в текущем такте времени должно сопровождаться перемещением вправо к прочтению следующего символа и изменением текущего состояния, которое должно определяться считанной в текущем такте буквой и состоянием, в котором автомат находится в текущем такте. Слово, имеющее длину l, автомат обрабатывает в течение l тактов. Итог прочтения слова «а» должен определяться состоянием, в котором автомат может оказаться после завершения обработки данного слова.

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

К={ A, Q, q0, g, F}.

Здесь:

1. А = {а1, а2, ..., an} является входным алфавитом.
2. Q = {q0, q1, q2, ..., qm} является множеством состояний автомата.
3. q0 является выделенным начальным состоянием автомата.
4. g является функцией переходов, определенной на множестве QxA = {(qi, 0)\i=l,..,m; j=1,...,n} и принимающей значения из множества Q (когда g(qi,aj) = qk, то это значит, что конечный автомат, который находился в состоянии qi , после прочтения буквы aj перешёл в состояние qk).
5. F является выделенным подмножеством (Fc Q), то подмножеством «хороших» состояний автомата.

Работа конечного автомата «К» по чтению входного слова а = ai1, ai2,…aip может быть представлена следующим образом. Пусть qa(t) будет обозначать состояние, в котором окажется автомат «К» после t тактов обработки текущего слова (здесь t=0,1,2,..., р):

• qa (0) = qо (перед началом работы автомат находился в состоянии q0), qa(1) = g(qa(0), ai.1) (прочитав первую букву, автомат переходит в состояние q« (1)).
• qа (2) = g (q a(1), ai2) (прочитав вторую букву, автомат переходит из состояния qa (1) в состояние qа (2)).
• qа(Р) = g(qа(Р - 1), aip) (прочитав все слово, автомат переходит из состояния qa(p-1) в состояние qа (Р)).

Считается, что слово «а» принято автоматом «К», если qa(p)ϵF , то есть после прочтения всего слова автомат должен находиться в одном из «хороших» состояний.

Пусть L(K) является совокупностью слов, которые принимает автоматом К. Совокупность L(K) именуется языком, который способен распознать данный конечный автомат «К». Язык L считается регулярным, если он может быть распознан некоторым конечным автоматом.

Конечный автомат, определяемый выражением:

К={ A, Q, q0, g, F},

Может быть удобно задан специальной диаграммой переходов. Диаграмма переходов является ориентированным графом, множество вершин которого совпадает с множеством состояний Q={q0, q1, q2, ..., qm} и если g(qi,aj)=qk, то из вершины, определяющей состояние qi, идет дуга к вершине, определяющей состояние qk, с надписанной над ней буквой aj. В случае, когда переход из qi в qk реализуется под воздействием любой из букв некоторого подмножества S (SϵA), все буквы этого подмножества надписываются над соответствующей дугой. При этом, вместо перечня всех букв допускается сокращенная запись «xϵS» или просто «S». Если вершина, определяющая состояние qi, входит в F, то на диаграмме она должна выделяться жирным кружком.

На рисунке ниже изображена диаграмма автомата K1, работающего над словами алфавита A={a, b, c}.

Рисунок 1. Диаграмма автомата K1. Автор24 — интернет-биржа студенческих работ

Автомат имеет два состояния, q0 и q1, причем «хорошим» считается лишь состояние q1.

Начав работу в состоянии q0, автомат под влиянием символов a, b из этого состояния не может выйти, а под влиянием символа «с» реализуется переход в состояние q1. Далее любой поступающий символ (буква) оставляет автомат в том же состоянии. Это означает, что автомат K1 распознает язык L1, который состоит из слов, имеющих в своем составе букву «с». Этот язык может считаться регулярным.