В контексте информатики слово - это конкатенация символов . Используемые символы называются алфавит . Например, некоторые слова, образованные из алфавита {0,1,2,3,4,5,6,7,8,9}, будут 1, 2, 12, 543, 1000 и 002.
A language - это подмножество всех возможных слов. Например, мы могли бы хотеть определить язык, который захватывает всех элитных агентов MI6. Все они начинаются с двойного 0, поэтому слова в языке будут 007, 001, 005 и 0012, но не 07 или 15. Для простоты мы говорим, что язык - это « над алфавитом» вместо «подмножества слов, образованных объединением символов в алфавите».
В информатике мы теперь хотим классифицировать языки. Мы называем язык обычным , если можно решить, находится ли слово в языке с помощью алгоритма / машины с постоянной (конечной) памятью, проверяя все символы в слове один за другим. Язык, состоящий только из слова 42, является регулярным, так как вы можете решить, находится ли слово в нем, не требуя произвольных объемов памяти; Вы просто проверяете, является ли первый символ 4, второй - 2, и следуют ли еще какие-либо числа.
Все языки с конечным числом слов являются регулярными, потому что мы можем (теоретически) просто построить дерево потока управления постоянного размера (вы можете представить его как набор вложенных if -статий, которые проверяют одну цифру после другой). Например, мы можем проверить, находится ли слово на языке «простых чисел от 10 до 99», с помощью следующей конструкции, не требующей памяти, кроме той, которая кодирует, в какой строке кода мы находимся в данный момент:
if word[0] == 1:
if word[1] == 1: # 11
return true # "accept" word, i.e. it's in the language
if word[1] == 3: # 13
return true
...
return false
Обратите внимание, что все конечные языки регулярны, но не все регулярные языки конечны; наш язык двойного 0 содержит бесконечное количество слов (007, 008, но также 004242 и 0012345), но может быть проверен с постоянной памятью: чтобы проверить, принадлежит ли ему слово, проверьте, первый символ - 0, а второй символ - 0. Если это так, примите это. Если слово короче трех или не начинается с 00, это не кодовое имя MI6.
Формально конструкция конечного автомата или регулярной грамматики используется для доказательства правильности языка. Они похожи на if -выступления выше, но допускают произвольно длинные слова. Если есть конечный автомат, есть и обычная грамматика, и наоборот, поэтому достаточно показать либо. Например, конечный автомат для нашего языка двойного 0:
start state: if input = 0 then goto state 2
start state: if input = 1 then fail
start state: if input = 2 then fail
...
state 2: if input = 0 then accept
state 2: if input != 0 then fail
accept: for any input, accept
Эквивалентная регулярная грамматика:
start → 0 B
B → 0 accept
accept → 0 accept
accept → 1 accept
...
Эквивалентное регулярное выражение :
00[0-9]*
Некоторые языки не обычные. Например, язык любого числа 1, за которым следует то же число 2 (часто записывается как 1 n 2 n , для произвольного n ) не является регулярным - вам нужно больше, чем постоянный объем памяти (= постоянное количество состояний), чтобы сохранить число 1 s, чтобы решить, есть ли слово в языке.
Обычно это следует объяснять в курсе теоретической информатики. К счастью, Википедия довольно хорошо объясняет и формальные и обычные языки .