Что такое обычный язык?

в контексте информатики, a слово - это конкатенация символы. Используемые символы называются алфавит. Например, некоторые слова, образованные из алфавита {0,1,2,3,4,5,6,7,8,9} будет 1,2,12,543,1000 и 002.

A язык тогда подмножество всех возможных слов. Например, мы могли бы определить язык, который захватывает всех элитных агентов MI6. Все начните с double-0, чтобы слова в языке были 007,001,005 и 0012, но не 07 или 15. Для простоты, мы говорим, что язык-это "over алфавит" вместо "подмножество слов, образованных конкатенацией символов на алфавит".

в информатике мы теперь хотим классифицировать языки. Мы называем язык обычный если это можно решить, если слово находится в языке с алгоритм / машина с постоянной (конечной) памятью, исследуя все символы в слове один за другим. Язык, состоящий только из слова 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

обратите внимание, что все конечные языки являются регулярными, но не все регулярные языки конечны; наш язык double-0 содержит бесконечное число слов (007,008, но и 004242 и 0012345), но может быть проверена с постоянной памятью: чтобы проверить, принадлежит ли слово в нем, проверьте, является ли первый символ 0, и является ли второй символ 0. Если это так, примите это. Если слово короче трех или не начинается с 00, это не кодовое имя МИ-6.

формально, конструкция a автомат или регулярные грамматики используется для доказывать, что язык является регулярным. Они похожи на 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ⁿ2ⁿ, для произвольного n) не является регулярным - вам нужно больше, чем постоянный объем памяти(= постоянное количество состояний) для хранения количества 1s, чтобы решить, является ли слово в языке.

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