Ограниченность

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

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

Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите Σ определены следующие константы:

· (пустое множество) ∅.

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

· (символьный литерал) «a», где a — символ алфавита Σ.

и следующие операции:

· (сцепление, конкатенация) RS обозначает множество {αβ | α ∈ R & β ∈ S}. Например, {«boy», «girl»}{«friend», «cott»} = {«boyfriend», «girlfriend», «boycott», «girlcott»}.

· (дизъюнкция, чередование) R|S обозначает объединение R и S. Например, {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}.^[4]

· (замыкание Клини, звезда Клини) R* обозначает минимальное надмножество множества R, которое содержит ε и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {«Go», «Russia»}* = {ε, «Go», «Russia», «GoGo», «GoRussia», «RussiaGo», «RussiaRussia», «GoGoGo», «GoGoRussia», «GoRussiaGo», …}.

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

Одно состояние определяется как начальное, а одно или более – как конечные

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

КА – это односторонний распознаватель без дополнительной памяти

Переходы оформляются в виде таблицы или графически, где для каждого состояния указывают следующее состояние и все возможные входные знаки

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего. Недетерминированный конечный автомат (НКА) является обобщением детерминированного.