Цепочки символов. Операции над цепочками символов

Формальные языки и грамматики

Вопросы

Построение конечного автомата по регулярной грамматике

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

Если задана регулярная грамматика G = <N, T, P, S>, правила вывода которой имеют вид: А –> аВ или А–>а, где А, В ∈ N, а ∈ Т. Тогда конечный автомат А= <V, Q, δ, q₀ , F>, задающий тот же самый язык, что порождает регулярная грамматика G, строится следующим образом:

1) V=T;

2) Q=N U {Z}, Z- заключительное состояние КА, не принадлежит N и T;

3) q₀= {S};

4) F={Z}

5) Отображение δ строится по правилам:

- каждому правилу подстановки в грамматике G вида А –> аВ ставится в соответствие команда (А,а) –> В;

- каждому правилу подстановки в грамматике G вида А –> а ставится в соответствие команда (А,а) –> Z.

Допустим обратный переход: конечному автомату А= <V, Q, δ, q₀ , F>можно поставить в соответствие регулярную грамматику G = <N, T, P, S>, у которой:

1) T=V;

2) N=Q;

3) S={ q₀};

4) Множество правил подстановки Р строится таким образом: каждой команде автомата (q_i, a) –> q_k ставится в соответствие правило подстановки q_i –> а q_k, если q_k ∈Q, либо q_i –> а, если q_k ∈Z, где Z – заключительное состояние.

1. Что называется регулярным выражением?

2. Какая существует взаимосвязь между регулярным выражением и распознаваемой лексемой?

3. Что такое регулярное множество?

4. Как можно доказать эквивалентность двух регулярных выражений?

5. Как можно доказать эквивалентность двух языков?

Цепочка символов – это произвольная последовательность символов, записанных один за другим. Понятие символа (или буквы) является базовым в теории формальных языков.

Цепочки символов обозначаются греческими буквами: a, b, g.

Цепочка – это последовательность, в которую могут входить любые допустимые символы. Цепочка – это необязательно некоторая осмысленная последовательность символов. Последовательность «аввв..аагрьь,.. лл» - тоже пример цепочки символов.

Для цепочки символов важен состав и количество символов в ней, а также порядок символов в цепочке. Один и тот же символ может произвольное число раз входить в цепочку, Поэтому цепочки «а» и «аа», а также «аб» и «ба» - это различные цепочки символов. Цепочки символов a и b равны (совпадают), a= b, если они имеют один и тот же состав символов, одно и тоже их количество и одинаковый порядок следования символов в цепочке.

Количество символов в цепочке называется длиной цепочки. Длина цепочки символа a обозначается как |a|. Очевидно, что если a=b, то и |a| =|b|.

Основной операцией над цепочками символов является операция конкатенации (объединения или сложения) цепочек.

Конкатенация (сложение, объединение) двух цепочек символов - дописывание второй цепочки в конец первой. Конкатенация цепочек a и b обозначается как ab. Выполнив конкатенацию цепочек просто: например, если a= «аб», а b= «вг», то ab = «абвг».

Так как в цепочке важен порядок символов, то операция конкатенации не обладает свойством коммутативности, то есть в общем случае a и b такие, что ab≠ba. Также очевидно, что конкатенация обладает свойством ассоциативности, то есть (ab)g=a(bg).

Еще одна операция - итерация (повторение) цепочки n раз, где nÎ N, n>0-это конкатенация цепочки самой с собой n раз. Итерация цепочки a n раз обозначается как aⁿ. Для операции повторения справедливы следующие равенства ∀ a: a¹ =a, a²=aa, a³=aaa, …и т.д.

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

Для пустой цепочки справедливы следующие равенства:

1. │ l│=0;

2. ∀a: la=al=a;

3. l₁=l;

4. ∀ n ≥ 0: lⁿ=l;

5. ∀ a:aº=l.

Дата добавления: 2014-12-27