Бесконечный язык против конечного языка

Мне неясно, как используются фразы «бесконечный» язык или «конечный» язык в компьютерной теории.

Я думаю, что корень проблемы в том, что такой язык, как , бесконечен в том смысле, что он может генерировать бесконечное (но счетное) количество строк. Тем не менее, он все еще может быть распознан конечным автоматом.$L=\{ab\}^*$

Также не помогает то, что книга Sipser на самом деле не делает этого различия (по крайней мере, насколько я могу судить). Вопрос о бесконечных / конечных языках и их связи с обычными языками возник в ходе пробного экзамена.

Боже мой Это похоже на путаницу, вызванную (старой школой) терминологией «язык конечных состояний» как синоним того, что сегодня известно как «обычный язык».

В любом случае, стандартные определения для конечного / бесконечного, принятые в эти дни, касаются только размера языка:

1. конечный язык любое множество строк, конечной мощности, | L | < $L$$|L|<\infty$ .
2. бесконечный язык любое множество строк, из бесконечного ( ℵ 0 ) мощности | L | = ∞ .$L$$\aleph_0$$|L|=\infty$

Конечная всегда регулярна.$L$

Бесконечный может быть регулярным (иногда называемым «конечным состоянием»), разрешимым (иногда называемым «рекурсивным»), нерегулярным (не конечным состоянием), неразрешимым и т. Д.,$L$

Язык - это набор строк. Конечно, если в нем есть конечное число строк.

Мне неясно, как используются фразы «бесконечный» язык или «конечный» язык в компьютерной теории.

Я думаю, что корень проблемы в том, что такой язык, как , бесконечен в том смысле, что он может генерировать бесконечное (но счетное) количество строк. Тем не менее, он все еще может быть распознан конечным автоматом.$L=\{ab\}^∗$

Другая проблема заключается в том, что теория формального языка довольно своеобразна тем, как она использует термин «язык».

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

Следовательно, в теории формального языка «язык» определяется просто как «набор строк». Обычно он не присваивает значения строкам в языке.

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

$ab$$\{ab\}$$ab$$ab$$\{ab\}$

$\{ab\}^*$${}^*$ обозначает функцию, которая отображает языки на языки: она отображает каждый язык $L$ на язык, состоящий из всех строк, которые состоят из строки в $L$ноль или более раз повторяется. Если$L$ это пустой язык, результат $L$; во всех остальных случаях результатом является бесконечный язык. Например,$\{ab\}^*$ это язык $\{ \epsilon, ab, abab, ababab, abababab, \ldots \}$, Это бесконечно, но с помощью оператора${}^*$мы можем описать это конечным образом, как $\{ab\}^*$,

Кроме того, мы можем использовать регулярное выражение для описания этого языка, а именно $(ab)^*$, Как и все регулярные выражения, это конечная строка, но, как и большинство регулярных выражений, которые содержат${}^*$ оператор, он описывает бесконечный язык.

Всякий раз, когда текст на формальных языках использует выражение, такое как $(ab)^*$это обозначает язык, спросите себя, обсуждает ли оно само регулярное выражение (например, как оно построено, какой язык он обозначает и т. д.) или просто использует регулярное выражение для ссылки на обозначаемый язык.