Теория формальных языков для чайников. Регулярные языки и конечные автоматы. Смотреть что такое "Регулярный язык" в других словарях

Регулярный язык

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

Определение регулярного множества

Пусть Σ - конечный алфавит. Регулярное множество R(Σ) в алфавите Σ определяется следующими рекурсивными свойствами:

См. также

• Построение синтаксического анализатора на основе автоматного подхода

Wikimedia Foundation . 2010 .

Смотреть что такое "Регулярный язык" в других словарях:

регулярный язык - — Тематики электросвязь, основные понятия EN regular language … Справочник технического переводчика

- (лат. regularius, от regula правило). Правильный, правильно устроенный, сделанный. Регулярный ход машины. Равномерный ход. Регулярная жизнь. Правильная, порядочная, однообразная жизнь. Словарь иностранных слов, вошедших в состав русского языка.… … Словарь иностранных слов русского языка

См … Словарь синонимов

Древнеписьменный язык - Язык с давними письменными традициями, т. е. получивший письменность, приспособленную к структуре данного языка, несколько веков тому назад, причем функционирование письменного варианта языка носило не эпизодический, а регулярный характер, при… … Словарь социолингвистических терминов

У этого термина существуют и другие значения, см. Кечуа. Кечуа Самоназвание: Qhichwa Simi, Runa Simi Страны … Википедия

Каркас здания с сеткой колонг или стоек, основанной на шаге одного размера (Болгарский язык; Български) равномерен скелет (Чешский язык; Čeština) pravidelný skelet (Немецкий язык; Deutsch) regelmäßiges Skelett (Венгерский язык; Magyar) szabályos… … Строительный словарь

- [ПАРК ФРАНЦУЗСКИЙ] парк, имеющий геометрически правильную планировку, обычно осевую схему (Болгарский язык; Български) френски парк (Чешский язык; Čeština) francouzský park (Немецкий язык; Deutsch) regelmäßiger Park; französischer Park… … Строительный словарь

Кечуа Самоназвание: Qhichwa Simi, Runa Simi Страны: Аргентина, Боливия, Колумбия, Перу, Чили, Эквадор Регионы: Анды Официальный статус: Перу … Википедия

Тагальский язык - (тагал, тагала, тагало; тагалог) один из филиппинских языков. Ареал первоначального распространения приходится на самый важный в политическом, экономическом и культурном отношении регион Республики Филиппины центральные и южные части острова… … Лингвистический энциклопедический словарь

Книги

• Производные глаголы. Секреты финской грамматики. Учебное пособие , Сафронов В. Д.. Пособие посвящено одному из интереснейших и недостаточно изложенных в русскоязычной учебной литературе разделов финской грамматики - производным глаголам. Они образуются от глаголов и от имен…

В этой главе мы начинаем изложение элементов теории формальных языков.

Говоря "формальный язык", мы имеем в виду то, что приведенные здесь результаты используются прежде всего при описании искусственных языков, придуманных людьми для специальных целей, например языков программирования. Но непреодолимой преграды между специально придуманными искусственными (формальными) языками и стихийно возникающими и развивающимися естественными языками не существует. Оказывается, что естественные языки характеризуются сложными грамматическими правилами, т.е. довольно жестко формализованы, а даже самый "научно разработанный" язык программирования содержит "темные места", однозначное понимание которых является проблемой.

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

Первый из них - синтаксис языка . Язык - это какое- то множество "слов", где "слово" есть определенная конечная последовательность "букв" - символов какого-то заранее фиксированного алфавита. Термины "буква" и "слово" могут пониматься по-разному (математическое определение этих терминов будет дано ниже). Так, "буквами" могут быть действительно буквы алфавита какого-нибудь естественного или формального языка, например русского языка или языка программирования "Паскаль". Тогда "словами" будут конечные последовательности "букв": крокодил", "integer ". Такие слова называют "лексемами". Но "буквой" может быть "слово" ("лексема") в целом. Тогда "слова" - это предложения естественного языка или программы языка программирования. Если фиксировано какое-то множество "букв", то не каждая их последовательность будет "словом", т.е. Элексемой" данного языка, а только такая последовательность, которая подчиняется определенным правилам. Слово "крыкадил" не является лексемой русского языка, а слово "iff" не является лексемой в "Паскале". Предложение "Я люблю ты" не является правильным предложением русского языка, точно так же, как и запись "х:= =t" не есть правильно написанный оператор присваивания "Паскаля". Синтаксис* языка и представляет собой систему правил, в соответствии с которыми можно строить "правильные" последовательности "букв". Каждое слово языка характеризуется определенной структурой, специфичной именно для данного языка. Тог да необходимо, с одной стороны, разработать механизмы перечисления, или порождения, слов с заданной структурой, а с другой - механизмы проверки того, что данное слово принадлежит данному языку. Прежде всего именно:эти механизмы и изучает классическая теория формальных языков.

Второй аспект - семантика языка . Семантика** предполагает сопоставление словам языка некоего "смысла", Эзначения". Например, записывая математическую формулу, мы должны соблюдать определенные синтаксические правила (расстановка скобок, правописание символов, порядок символов и т.п.), но, кроме этого, формула имеет вполне определенный смысл, что-то обозначает.

Язык - это средство общения, передачи информации. Если мы хотим, чтобы нас поняли, мы должны не только синтаксически правильно, соблюдая должный порядок букв в слове и слов в предложении, строить свою речь, но и заботиться об ее смысле, о тех идеях, которые мы выражаем в речи. Математические теории "смысла" появились сравнительно недавно, и в дополнении к следующей главе мы очень коротко рассмотрим некоторые подходы к математическому описанию семантики языков программирования.

* Слово "синтаксис" происходит от древнегреческих "syn" - "вместе" и "taxis" - "порядок, строй". Таким образом, синтаксис можно понимать как "составление".

** От древнегреческих слов "sema" - "знак, знамение" и "semanticos" - "обозначающий".

Наконец, третий аспект - прагматика языка . Прагматика связана с теми целями, которые ставит перед собой носитель языка: например, человек произносит речь, имея перед собой цели, связанные не с синтаксисом, не с семантикой языка, на котором он говорит или пишет, а, скажем, с получением за речь определенной суммы денег. Прагматика является уже скорее дисциплиной социально-философской, затрагивающей целепол агающую деятельность личности. Мы ни в малейшей степени не будем ее касаться.

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

• Алфавит, слово, язык

• Порождающие грамматики

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

Теория автоматов - это раздел теории управляющих систем , изучающий математические модели преобразователей дискретной информации, называемые автоматами . С определенной точки зрения такими преобразователями являются как реальные устройства (вычислительные машины, автоматы, живые организмы и т.д.), так и абстрактные системы (например, формальная система, аксиоматические теории и т.д.), благодаря чему возможно применение теории автоматов в различных научных и прикладных исследованиях. Наиболее тесно теория автоматов связана с математической логикой и теорией алгоритмов. В частности, средствами теории автоматов доказывается разрешимость некоторых формальных исчислений.

Еще одним важнейшим объектом изучения в данном курсе является формальный язык 1 – произвольное множество слов некоторого алфавита. Важность формальных языков для теоретической информатики обусловлена тем, что наиболее простой и удобной моделью данных, используемых в компьютерных программах, является конечная последовательность, каждый элемент которой взят из некоторого заранее зафиксированного конечного множества. Поскольку используемые в приложениях формальные языки, как правило, являются бесконечными, то нужен способ конечного описания формального языка. В данном курсе будем изучать 3 классических средства такого описания: автоматы , регулярные выражения и порождающие грамматики .

Введение

1. Начальные понятия теории формальных языков

Рассмотрим непустое конечное множество А , состоящее из символов {a 1 , …, a k }. Будем называть А алфавитом , а его символы – буквами . Всякая конечная последовательность букв этого алфавита называется словом (цепочкой или строкой ): w =a 1 a 2 …a n – слово (a i A ), |w | – длина слова (число букв, из которых состоит слово, причем каждый символ встречается столько раз, сколько раз он встречается в w ). Через |w | b обозначим количество вхождений символа b в слово w .

Бесконечная последовательность букв алфавита А называется сверхсловом , - сверхслово из бесконечного числа букв а . Пустым называется слово, не содержащее ни одной буквы. Оно обозначается через . Очевидно, ||=0.

- множество слов алфавита А длины n . Множество всех слов алфавита А (включая сверхслова) обозначается А *. Это множество счетное, поскольку является объединением счетного числа конечных множеств
. Множество всех непустых слов в алфавите А обозначается А + . Если A ={a }, то А *={a }* будем обозначать через а *.

Любое подмножество
называетсяязыком (формальным языком ) над алфавитом А .

Если x и y – слова языка
, то слово ху (результат приписывания слова у в конце слова х ) называется конкатенацией (сцеплением , произведением ) слов х и у .
(n раз берем х ). Положим
.

Говорят, что слово х – подслово слова у , если y =uxv для некоторых слов u и v . Все подслова слов языка
образуютмножество подслов языка L , которое обозначается через Subw(L ).

Примеры . 1. ba 3 =baaa ,
- в данном слове есть подслова ab , aba , ba и т.п.

2. Множество {a , abb } - язык (конечный) над алфавитом {a , b }.

3. Множество
является языком над алфавитом {a , b }. Этот язык бесконечный, он содержит слова b , ba , aba , baa , abaa , baaa , aabaa , abaaa и т.д.

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения и разности языков, заданных над одним и тем же алфавитом. Так, язык
, где
, называется дополнением языкаL относительно алфавита А . И если  всегда включено в А *, то язык
может как содержать, так и не содержать его. В последнем случае
.

Пусть ,
. Тогда языкназываетсяконкатенацией (сцеплением , произведением ) языков и . При этом
,
(n раз), если n >0.

Примеры . 1. Если
,
,то .

2. Если L={0, 01}, то
.

Итерацией языка L называется язык
(эта операция называется также звездочкой Клини ). Язык
называется позитивной итерацией языка L .

Пример . Если A ={a , b } и L ={aa , ab , ba , bb }, то
.

Обращением или зеркальным образом слова w называется слово w R , в котором буквы слова w идут в обратном порядке. Например, если w =bac , то

Пусть
. Тогда язык
называетсяобращением языка L .

Всякое начало слова будем называть префиксом , а всякий конец слова – суффиксом . Например, если y =xv , то х – префикс слова у (обозначение – х [y ), а v – суффикс слова у (обозначение – v ]y ). Очевидно, что пустое слово является как префиксом, так и суффиксом любого слова. Все префиксы слов языка
формируютмножество префиксов этого языка: Pref(L )
. АналогичноSuf(L )
-м ножество суффиксов языка
.

Если язык L таков, что никакое слово L не является префиксом (суффиксом) никакого другого слова L , то говорят, что L обладает префиксным (суффиксным) свойством .

Пусть А 1 и А 2 – алфавиты. Если отображение f :
удовлетворяет условиюдля всех слов
и
, то отображениеf называется гомоморфизмом .

Замечания. 1. Можно доказать, что если f – гомоморфизм, то
.

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

3. Применяя гомоморфизм к языку L , получаем другой язык f (L ).

Если f :
– гомоморфизм,
и
, то черезf (L 1) обозначается язык
, а через
обозначается язык
, а само отображение
называетсяобращением гомоморфизма .

Примеры . 1. Допустим, мы хотим заменить каждое вхождение в цепочку символа 0 на символ а , а каждое вхождение 1 – на bb . Тогда можно определить гомоморфизм f так, что
и
. Если
, то
.

2. Пусть f – гомоморфизм, для которого
и
. Тогда
и
.

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

Утверждение

Язык является РМ тогда и только тогда, когда он задан леволинейной (праволинейной) грамматикой. Язык может быть задан леволинейной (праволинейной) грамматикой тогда и только тогда, когда он является регулярным множеством.

Язык является РМ тогда и только тогда, когда он задан с помощью конечного автомата. Язык распознается с помощью конечного автомата тогда и только тогда, когда он является РМ.

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

Например, для нахождения регулярного выражения для языка, заданного праволинейной грамматикой, необходимо построить и решить систему уравнений с регулярными коэффициентами.

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

Для построения КА на основе известной регулярной грамматики ее необходимо привести к автоматному виду. Множество состояний автомата будет соответствовать множеству нетерминальных символов грамматики. 2.3.2 Свойства регулярных языков

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

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

Для регулярных языков разрешимы многие проблемы, неразрешимые для других типов языков. Например, следующие проблемы являются разрешимыми независимо от того, каким из способов задан язык:

Проблема эквивалентности: Даны два регулярных языка L 1 (V) и L 2 (V). Необходимо установить, являются ли они эквивалентными.

Проблема принадлежности цепочки языку. Дан регулярный язык L(V), цепочка символов V * . Требуется проверить, принадлежит ли эта цепочка языку.

Проблема пустоты языка. Дан регулярный язык L(V). Необходимо проверить, является ли этот язык пустым, т.е. найти хотя бы одну цепочку, L(V).

Иногда бывает необходимо доказать, является дли некоторый язык регулярным. Если возможно задать этот язык одним из рассмотренных способов, то он является регулярным. Но если такой способ найти не удается, неизвестно, то ли язык не является регулярным, то ли просто не удалось найти способ его задания. Существует простой метод проверки, является ли рассматриваемый язык регулярным. Доказано, что если для некоторого языка выполняется т.н. лемма о разрастании, то он является регулярным. Если же эта лемма не выполняется - язык не регулярный.

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

Формально лемма записывается так. Если дан язык L, то константа p>0, такая, что если L и p, то цепочку можно записать в виде, где 0

Пример. Рассмотрим язык L={a n b n n>0}. Докажем, что он не является регулярным, используя для этого лемму о разрастании языков.

Пусть этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка = a n b n и запишем ее в виде. Если a + или b + , то тогда цепочка i не принадлежит языку для любого i, что противоречит условиям леммы. Если же a + b + , то цепочка 2 также не принадлежит языку L. Получили противоречие, следовательно, язык не является регулярным.

Регулярные множества и регулярные выражения

Регулярные множества

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

Определение 1. Пусть V 1 и V 2 - множества цепочек. Определим три операции на этих множествах.

Объединение: V 1 V 2 ={|   V 1 } или   V 2 .

Конкатенация (произведение, склеивание): Vl V2 = {|  V 1 ,  V 2 } Знак операции конкатенации обычно опускается.

Пример: V, = {abc, ba},V 2 = {b, cb}. V1V2 ={abcb, abccb, bab, bacb}.

Обозначим V n произведение n множеств V:V n =VV...V,V° ={} (здесь -пустая цепочка).

Пример: V 1 = {abc, ba}, V 1 2 = {abcabc, abcba, baba, baabc}.

3. Итерация: V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

Пример: V = {a, bc}, V* = {, a, bc, aa, abc, bcbc, bca, aaa, aabc,...}.

Определение 4.13. Класс регулярных множеств над конечным словарем V опреде ляется так:

объединение ST;

конкатенация ST;

итерация S* и Т*.

5. Если множество не может быть построено конечным числом применения правил 1-4, то оно нерегулярно.

Примеры регулярных множеств: {ab, ba}* {aa}; {b}({c}{d, ab}*). Примеры нерегулярных множеств: {a n b n | n > 0}; { | в цепочке  количества вхождений символов а и b совпадают}.

Регулярные выражения

Регулярные множества хороши тем, что их можно очень просто описать формула­ми, которые мы назовем регулярными выражениями.

Определение 2. Класс регулярных выражений над конечным словарем V опреде ляется так:

их сумма R1+R2;

их произведение R1R2;

их итерация R1* и R2*.

4. Если выражение не построено конечным числом применения правил 1-3, то оно не является регулярным.

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

Примеры регулярных выражений: ab + bа*; (аа)*b + (с + dab)*.

Очевидно, что регулярные множества и регулярные выражения весьма близки. Но они представляют собой разные сущности: регулярное множество - это множество цепочек (в общем случае бесконечное), а регулярное выражение - это формула, схематично показывающая, как было построено соответствующее ей регулярное множество с помощью перечисленных выше операций (и эта формула конечна).

Пусть R ^ - регулярное множество, соответствующее регулярному выражению R. Тогда:

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

Рассмотрим примеры регулярных выражений и соответствующих им языков.

Очевидно, что множество цепочек регулярно тогда и только тогда, когда оно может быть представлено регулярным выражением. Однако одно и то же множество цепочек может быть представлено различными регулярными выражениями, например, множество цепочек, состоящее из символов а и содержащее не менее двух а может быть представлено выражениями: аа*а; а*ааа*; ааа*; а*аа*аа* и т. д.

Определение 3. Два регулярных выражения R1 и R2 называются эквивалентными (обозначается Rl = R2) тогда и только тогда, когда R 1 ^ = R 2 ^ .

Таким образом, аа*а = а*ааа* = ааа* = а*аа*аа*. Возникает вопрос, как определить эквивалентность двух регулярных выражений.

Теорема 1 . Для любых регулярных выражений R, S и Т справедливо:

Эти соотношения можно доказать, проверяя равенство соответствующих множеств цепочек. Их можно использовать для упрощения регулярных выражений. Например: b (b + aa*b) = b (b + aa*b) = b ( + aa*) b = ba*b. Отсюда b (b + aa*b) = ba*b, что неочевидно.

Теорема Клини

Регулярные выражения - это конечные формулы, задающие регулярные языки. Но подобным же свойством обладают и конечные автоматы - они тоже задают языки. Возникает вопрос: как соотносятся между собой классы языков, задаваемые конечными автоматами и регулярными выражениями? Обозначим А множество автоматных языков, R - множество регулярных языков. Стефен Клини, американский математик, доказал следующую теорему.

Теорема 2 . (Теорема Клини.) Классы регулярных множеств и автоматных языков совпадают, то есть А = R .

Иными словами, каждый автоматный язык может быть задан формулой (регулярным выражением) и каждое регулярное множество может быть распознано конечным автоматом. Мы докажем эту теорему конструктивно, в два шага. На первом шаге докажем, что любой автоматный язык является регулярным множеством (или, что то же, для любого конечного автомата можно построить регулярное выражение, задающее распознаваемый этим автоматом язык). На втором шаге докажем, что любое регулярное множество является автоматным языком (или, что то же, по любому регулярному выражению можно построить конечный автомат, допускающий в точности цепочки соответствующего регулярного множества).

Введем в рассмотрение модель графа переходов как обобщение модели конечного автомата. В графе переходов одна начальная и произвольное количество заключительных вершин, а направленные ребра помечены, в отличие от конечного автомата, не символами, а регулярными выражениями. Граф переходов допускает цепочку а, если а принадлежит множеству цепочек, описываемую произведением регулярных выражений R 1 R 2 ...R n , которые помечают путь из начальной вершины в одну из заключительных вершин. Множество цепочек, допускаемых графом переходов, образует допускаемый им язык.

Рис. 1. Граф переходов

На рис. 1 изображен граф переходов, который допускает, например, цепочку abbca, поскольку путь s->r->p->s->r->q, который ведет в заключительное состояние q, помечен цепочкой регулярных выражений ab*c*а. Конечный автомат является частным случаем графа переходов и поэтому все языки, которые допускаются автоматами, допускаются и графами переходов.

Теорема 3. Каждый автоматный язык является регулярным множеством, А  R .

Доказательство. Граф переходов с одной начальной и одной заключительной вершинами, у которого единственное ребро из начальной в заключительную вершину помечено регулярным выражением R, допускает язык R ^ (рис. 1).

Рис. 2. Граф переходов, допускающий регулярный язык FT

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

Любой конечный автомат и любой граф переходов всегда можно представить в нормализованной форме, в которой только одна начальная вершина только с исходящими ребрами и только одна заключительная вершина только с входящими ребрами (рис. 3).

Рис. 3. Граф переходов с одной начальной и одной заключительной вершинами

С графом переходов, представленным в нормализованной форме, могут быть выполнены две операции редукции - редукция ребра и редукция вершины - с со­хранением допускаемого этим графом переходов языка:

а) редукция ребра:

Б ) редукция вершины (замена выполняется для каждого пути, проходящего через вершину р, с последующим ее выбрасыванием как недостижимого состояния):

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

Пример

Пусть задан конечный автомат А:

Строим эквивалентный граф переходов в нормализованном виде.

Редукция вершины 3:

Редукция дуг и применение правила R = R:

Редукция вершины 2:

Редукция дуги и вершины 1:

Таким образом язык, распознаваемый автоматом А, задается регулярным выраже­нием: R A = b+(a+bb)(b+ab)*a.

Докажем теорему Клини в другую сторону.

Теорема 2. Каждое регулярное множество является автоматным языком: R  A .

Доказательство. Покажем, что для каждого регулярного выражения R может быть построен конечный автомат A r (возможно, недетерминированный), распознающий язык, задаваемый R. Определение таких автоматов дадим рекурсивно.

(начальное и заключительное состояния А совмещаются).

Пример (продолжение)