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

Question

Я пытаюсь понять концепцию уровней языка (обычный, контекстно-зависимый, контекстно-зависимый и т. Д.).

Я могу легко это найти, но все объяснения, которые я нахожу, - это набор символов и разговоры о множествах. У меня есть два вопроса:

1. Можете ли вы описать словами, что такое обычный язык и как эти языки отличаются?

2. Где люди учатся понимать это? Как я понимаю, это формальная математика? У меня было несколько курсов в универе, которые использовали его, и почти никто не понимал этого, поскольку преподаватели просто предполагали, что мы это знали. Где я могу узнать это и почему люди "ожидают" знать это во многих источниках? Это как пробел в образовании.

Вот пример:

Любой язык, принадлежащий этому набору, является обычным языком по алфавиту.

Как язык может быть "над" чем-либо?

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

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

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

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

Answer 3

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

Вот содержимое:

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