Ответ 1
В контексте информатики слово представляет собой конкатенацию символов. Используемые символы называются алфавитом. Например, некоторые слова, сформированные из алфавита {0,1,2,3,4,5,6,7,8,9}, были бы 1, 2, 12, 543, 1000 и 002.
Язык - это подмножество всех возможных слов. Например, нам может понадобиться определить язык, который захватывает всех элитных агентов MI6. Все начинаются с double-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 in the language
if word[1] == 3: # 13
return true
...
return false
Заметим, что все конечные языки являются регулярными, но не все регулярные языки конечны; наш язык double-0 содержит бесконечное число слов (007, 008, но также 004242 и 0012345), но может быть проверено с постоянной памятью. Чтобы проверить, принадлежит ли это слово, проверьте, первый символ 0, а второй символ 0. Если это случай, примите его. Если слово короче трех или не начинается с 00, это не кодовое имя MI6.
Формально конструкция конечного автомата или регулярная грамматика используется для доказательства того, что язык является регулярным. Они аналогичны приведенным выше if -знакам, но допускают сколь угодно длинные слова. Если есть машина конечного состояния, есть также регулярная грамматика, и наоборот, поэтому достаточно показать ее. Например, конечный автомат для нашего языка double-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, чтобы решить, находится ли на нем слово.
Это обычно объясняется в теоретическом курсе по информатике. К счастью, Wikipedia объясняет как formal, так и обычные языки красиво.