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

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

Это обычно объясняется в теоретическом курсе по информатике. К счастью, Wikipedia объясняет как formal, так и обычные языки красиво.

Ответ 2

Вот некоторые из эквивалентных определений из Wikipedia:

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

• он может быть принят детерминированной машиной конечного состояния.
• он может быть принят недетерминированной машиной конечного состояния

• его можно описать формальным регулярным выражением.

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

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

Одна из самых важных характеристик заключается в том, что в отличие от контекстно-свободных языков, обычный язык не поддерживает произвольную вложенность/рекурсию, но у вас есть произвольное повторение.

Язык всегда имеет базовый алфавит, который является набором разрешенных символов. Например, алфавит языка программирования обычно либо является ASCII, либо Unicode, но в формальной теории языков также хорошо говорить о языках над другими алфавитами, например, двоичный алфавит, где разрешены только символы 0 и 1.

В моем университете нас учили теории формального языка в классе Compilers, но это, вероятно, отличается между разными школами.

Ответ 3

Я узнал большую часть такого рода из "Введение в теорию вычислений" Майкла Сипсера; Я нашел его полезным.

Вот содержание:

• Введение
• Часть 1: Автоматы и языки
  • 1. Регулярные языки
  • 2. Языки без контекста
• Часть 2: Теория вычислимости
  • 3. Тезис о Церкви-Тьюринга
  • 4. Разрешимость
  • 5. Приводимость
  • 6. Расширенные темы теории вычислимости
• Часть 3: Теория сложности
  • 7. Сложность времени
  • 8. Космическая сложность
  • 9. Труднорешаемые
  • 10. Расширенные темы в теории сложности.