Бесконечный язык не может быть регулярным? Что такое конечный язык?
Я прочитал это в книге о вычислимости:
(Теорема Клини). Язык является регулярным тогда и только тогда, когда его можно получить из конечных языков, применяя объединение трех операций, конкатенацию, повторение конечное число раз.
Я борюсь с "конечными языками".
Рассмотрим этот язык: L = a*
Это не конечно. Это набор {0, a, aa, aaa, ...} который явно бесконечное множество (0 = пустая строка).
Так что это бесконечный язык, верно? То есть "бесконечный набор" означает "бесконечный язык", верно?
Очевидно, что a* это обычный язык. И это бесконечный язык. Таким образом, по теореме Клини он не может быть регулярным языком. Противоречие.
Я не совсем понимаю. Я думаю, что я не знаю, что означает "конечный язык".
5 ответов
Вы на правильном пути, это может быть яснее. Теорема Клина выражает эквивалентность трех утверждений
Язык является регулярным == Язык может быть выражен с помощью регулярного выражения == Язык может быть выражен с помощью конечных автоматов.
Ваш пример действительно обычный язык. Конечный язык - это то, что вы ожидаете, язык, который можно перечислить за ограниченное количество времени.
Когда они говорят о повторении, они говорят об операции Kleen Star, которая именно a* представляет собой набор {empty, a, aa, aaa, aaaa, ...}
РЕДАКТИРОВАТЬ:
Я нашел эту ссылку: теорема Клиниса, которая очень помогает. Если под "повторением" подразумевается "Клин Стар", то оригинальное утверждение имеет смысл. a* является Kleen_Star(a)
Очень скоро ваше утверждение говорит:
Язык является регулярным тогда и только тогда, когда для него существует регулярное выражение.
Часть "может быть получена из конечных языков путем применения объединения трех операций, конкатенации, повторения конечного числа раз" по сути является быстрым словесным определением регулярного выражения. Обычно регулярное выражение (RE) определяется формально, начиная со следующих базовых случаев:
- ∅ (пустой набор) является RE
- ε (пустая строка) является RE
- а является RE, где а находится в алфавите
Это все конечные языки. Затем мы получаем другие RE, применяя следующие три рекурсивных правила конечное число раз:
- A | B является RE, где и A, и B являются RE
- AB является RE, где и A, и B являются RE
- A* является RE, где A является RE
В конце концов, вы можете создавать бесконечные языки, используя конечные описания (регулярное выражение).
Конечный язык - это язык, содержащий конечное число слов. Простейшие случаи - это те, которые вообще не содержат слов, пустой строки и одной строки, состоящей из одного символа (например, a в твоем примере).
Я думаю, что ваше замешательство происходит из-за неправильного понимания правила, которое вы цитируете (как и некоторые из тех, кто комментирует вопрос)
(Теорема Клини). Язык является регулярным тогда и только тогда, когда его можно получить из конечных языков, применяя объединение трех операций, конкатенацию, повторение конечное число раз.
Этот отрывок говорит не о количестве операций над строками, необходимыми для создания всех строк в языке, а о количестве операций на более простых языках, необходимых для определения определяемого языка. Язык, который вы упоминаете, создается, начиная с конечного языка (set {"a"}) и применяя оператор повторения один раз.
Другой и менее прямой способ поставить точку зрения будет апеллировать не к языкам и операциям над языками, а к выражениям, обозначающим языки, и к более сложным выражениям, сочетающим их: язык является регулярным тогда и только тогда, когда его можно обозначить с помощью регулярного выражения, содержащего конечное число операторов.
Принять выражение как aобозначает конечный язык, содержащий только одно слово "а". Мы можем добавить один оператор повторения к этому выражению, и мы получаем a*бесконечный язык, содержащий каждую конкатенацию от нуля или более слов из первого языка. Каждое конечное выражение E мы можем построить, начиная с выражений, обозначающих конечные языки, и комбинируя одно или два меньших выражения F и G, используя шаблоны E = F | G, E = FG или E = F * будет обозначать обычный язык. Выражения, обозначающие конечные языки (языки с конечным числом слов), являются базовым случаем, когда правило выражается в терминах выражений; конечные языки являются базовым случаем, когда правило изложено непосредственно в терминах языков, без каких-либо обходных путей.
Если мы допустим, чтобы объединение, конкатенация и повторение применялись бесконечно много раз (или эквивалентно, если мы разрешаем бесконечные выражения, используя правила для регулярных выражений), результирующий язык не гарантируется регулярным. Это аналог на уровне регулярного языка наблюдения, согласно которому бесконечно большие контекстно-свободные грамматики могут определять неконтекстно-свободные языки, как показано грамматиками van Wijngaarden.
Язык с конечным числом строк - это конечный язык.
Поскольку строки конечны , их можно использовать для создания конечного автомата. Теорема Клини состоит в том, что (1) любой регулярный язык принимается конечным автоматом. Верно и обратное: (2) любой язык, принимаемый конечным автоматом, является регулярным. Обратите внимание, что автомат может быть или не быть детерминированным.
Теперь, когда язык бесконечен (он имеет бесконечное количество строк), это может быть любой тип языка (обычный или нет) в иерархии Хомского.
Бесконечный язык означает множество, имеющее бесконечные классы эквивалентности. Однако язык a* имеет только один класс эквивалентности, что делает его конечным языком.