Теория формальных языков и автоматы

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

Definition

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

Scope

Охватывает иерархию Хомского (регулярные, контекстно-свободные, контекстно-зависимые, рекурсивно перечислимые языки), соответствующие грамматики и распознающие автоматы — конечные автоматы, магазинные автоматы и машины Тьюринга. Рассматриваются свойства замыкания и разрешимости, имеющие отношение к обработке языка, и вопрос о том, где естественный язык находится в этой иерархии. Леммы о накачке и полные доказательства сложности рассматриваются как фоновый, а не основной материал.

Core questions

• Какой автомат соответствует каждому уровню иерархии Хомского?
• Где естественный язык находится в иерархии и почему утверждается, что он превосходит контекстно-свободную мощность?
• Что означает для класса языков быть замкнутым относительно операции, и почему это важно для инженерии?

Key concepts

• регулярный язык
• контекстно-свободная грамматика
• контекстно-зависимая грамматика
• конечный автомат
• магазинный автомат
• машина Тьюринга
• свойства замыкания
• слабая контекстная зависимость

Key theories

Иерархия Хомского

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

Соответствие грамматика–автомат

Каждый класс грамматик доказуемо эквивалентен классу машин — регулярные грамматики конечным автоматам, контекстно-свободные грамматики магазинным автоматам — связывая генеративные описания с алгоритмами распознавания.

History

В работе Хомского 1956 года была представлена иерархия как часть аргументации того, что конечно-автоматные модели неадекватны для естественного языка. Последующие десятилетия формализовали соответствия автоматов, а позже вычислительные лингвисты показали, что естественный язык требует максимум «слабо контекстно-зависимой» мощности, что мотивировало грамматические формализмы, выходящие за рамки контекстно-свободных.

Debates

Является ли естественный язык контекстно-свободным?

Перекрестные зависимости в таких языках, как швейцарский немецкий, использовались для аргументации того, что естественный язык превосходит контекстно-свободную мощность, что привело к понятию слабой контекстной зависимости как правильного уровня выразительности.

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

В чем разница между регулярным и контекстно-свободным языком?

Регулярные языки могут быть распознаны с конечной памятью конечным автоматом; контекстно-свободные языки могут требовать стека (магазинного автомата) для отслеживания вложенной структуры, такой как сбалансированные скобки или вложенные предложения.