Важные понятия для описания формального языка: «алфавит» или множество символов, «цепочка» или последовательность символов некоторого алфавита, «язык» или множество цепочек в одном и том же алфавите.
Алфавит
Алфавитом называют непустое конечное множество символов, Будем обозначать – ∑. В качестве примеров можно ввести следующие описания множества:
- Бинарный или двоичный алфавит - ∑={0, 1}
- Множество строчных букв английского алфавита - ∑= {a, b, …,z}
Цепочка
Цепочкой (словом) будем называть конечную последовательность символов некоторого алфавита: 1010, 001; пустая цепочка - это цепочка, не содержащая ни одного символа, e - обозначение пустой цепочки.
Длина цепочки
Длина цепочки – это число позиций символов в цепочке. Обозначается - | w |. Например, цепочка 110011 имеет длину 6.
Степени алфавита
Если ∑ - некоторый алфавит, то используя знак степени над ∑, можно описать множество цепочек определенной длины. Определим ∑j как множество всех цепочек длины j, состоящих из символов алфавита ∑.
Пусть ∑ ={0, 1} есть алфавит, тогда ∑0={e}, ∑1={0, 1}, ∑2={00, 01, 10, 11}, ∑3={000, 001, 010, 011, 100, 101, 110, 111} и т.д. есть степень алфавита. Таким образом, элементом множества ∑0 есть единственный элемент – пустое множество e, элементом множества ∑1 являются элементы самого алфавита, элементом множества ∑2 являются пары xy, где x и y принадлежат алфавиту ∑, а элементом множества ∑n будет n-ка элементов алфавита ∑.
Отметим, что ∑0={} независимо от алфавита ∑, т.е. e - единственная цепочка длины 0.
Множество всех цепочек над алфавитом ∑ обозначим через ∑*. Например, {0,1}*={e, 0, 1, 00, 01, 10, 11,000,…}. Эквивалентная запись - ∑*=∑0 ∪ ∑1 ∪ ∑2 ∪…
Конкатенация цепочек
Пусть x и y цепочки. Введем операцию конкатенация (соединение) цепочки x и y, результатом которой будет новая цепочка, в которой последовательно записаны цепочки x и y. В общем случае, если x – цепочка из i символов: x = a1, a2,…, ai, а y = b1, b2, , bj, то xy – это цепочка длины w=i+j: xy = a1, a2,…, ai, b1, b2, , bj.
Пусть x = 011010 и y = 011, тогда xy = 011010011. Далее, для любой цепочки z справедливо равенство z=ze=z, то есть e - является единицей (нейтральным элементом) относительно операции конкатенации. Результат конкатенации e с любой цепочкой дает ту же самую цепочку. (Аналогия – 0 есть нейтральный элемент относительно операции.
Язык
Множество цепочек, каждая из которых принадлежит ∑*, где ∑ - некоторый фиксированный алфавит, называется языком. Если ∑ - алфавит, то L ⊆∑* - язык над алфавитом ∑. Язык L над алфавитом содержит цепочки, в которые входят символы алфавита (не обязательно все). Поэтому можно утверждать, что, если L является языком над, то L – это язык над любым алфавитом, содержащим ∑.
Регулярное выражение
Регулярное выражение – есть инструмент, использующийся для формального описания языка. Итак, требуется описать некоторый язык над алфавитом ∑. Следует ввести правила, описывающие элементы этого языка с помощью некоторых шаблонов
Регулярным выражением над ∑ будут являться:
- любые элементы алфавита ∑.
- пустая строка ε.
- результаты операций с регулярными выражениями над ∑. Перечень операций включает: объединение -, конкатенации или присоединения, замыкание Клини - * (звездочка). Таким образом, если a и b – любые регулярные выражения над ∑, то результаты операций (a υ b), (ab) и a* - есть регулярные выражения.
Язык, описываемый регулярным выражением a, обозначается L(a).
Пример алфавита и регулярных выражений над ним – алфавит ∑ = {a, b, c}. Поскольку элементы алфавита по определению являются регулярными выражениями, то конструкции типа (ab)*, (a υ b), (a υ b)*, (a υ b), (c(a υ b)(bυc)).
Регулярному выражению вида (a υ b) соответствуют все строки от выражения a и все строки от выражения b. Так, если L(a) соответствуют строки «aa», «abab», L(b) – «bb», «babb», то выражению (a υ b) соответствует – L(((a b))) со строками «aa», «abab», «bb», «babb».
Регулярному выражению (ab) соответствует язык, состоящий из строк вида xy, где x – некоторая строка из L(a), а y – строка из языка L(b). Эта операция носит название конкатенация. Для L(a) и L(b), представленных выше, язык L((ab)) = {«aabb», «aababb», «ababbb», «ababbabb»}.
Регулярному выражению a* (символ * носит название замыкание Клини) соответствует язык, состоящий из строк ε, s1, s1s2…, где sj – любая строка из языка L(a). Если язык L(a) = {«ab», «bbbb»}. Тогда L(a*) = { ε, «ab», «abab», «bbbb», «abbbbb»…}.
Эквивалентность регулярных выражений: ради упрощения записи сложных выражений используется приоритеты операций: сначала исполняется замыкание Клини, затем конкатенация и после этого – операция объединение. Поэтому справедливо следующая запись:
((ab) (bb)) = ab υ bb;
a(b(cd) = abcd.
Краткий вывод по изобразительным возможностям регулярных выражений. На вопрос – можно ли с помощью регулярных выражений описать любой язык – ответ будет отрицательным, так даже заведомо простые языки вида {«ab», «aabb», «aaabbb», …} невозможно формально описать регулярными выражениями. Дело в том, что языки на базе регулярных выражений, называются регулярными языками, и они составляют ограниченный класс языков. Полезность регулярных языков состоит в том, что простые операции порождения создают часто встречаемые на практике языки. Любой язык, состоящий из конечного числа строк, является регулярным языком. Например, язык L = {«bb», «abc», «bab», «c»} описывается регулярным выражением bb υ abc υ bab υ c.
Автомат
Возможности формального описания языков средствами регулярных выражений ограничены классом регулярных языков. Поэтому следует обратить внимание на другие инструментальные средства описания языков. К ним относятся конечные автоматы (детерминированные и недетерминированные), которые используются для описания формальных языков.
Автомат следует рассматривать как теоретическую модель вычислительной машины или некоторого алгоритма вычислений.
Формальная грамматика
Теория компиляции, относящаяся к распознаванию синтаксических структур, основывается на теории контекстно-свободных грамматик.
Формальное определение синтаксиса языка программирования называется грамматикой.
Грамматика состоит из набора правил (правил подстановки или продукций), определяющих последовательности символов, которые образуют допустимые для данного языка программы.
Формальная грамматика – это грамматика, в которой используется строго определенная система обозначений.
В технологии компиляции находят применение два класса грамматик: НФБ-грамматика (нормальная форма Бэкуса или контекстно-свободная грамматика) и регулярная грамматика.
Ниже будет рассмотрена НБФ-грамматика.
Похожие статьи:
