История изменений

Исправление invy, 09.01.15 14:30 (текущая версия) :

Ты серьёзно?

Всё не так совершенно.

Языки подразделяются на типы (иерархия Хомского): регулярные (тип 3), контекстно-свободные (тип 2), контекстно-зависимые (тип 1), и рекурсивно перечисляемые (тип 0). Это просто иерархия. Как... с алкоголем. Есть слабо-алкогольные, крепкие...

Не надо смешивать это с алфавитом.

Над алфавитом T = {a, b, c} можно построить все виды языков. Регулярный L = {abc} (конечный, одно слово abc), или L = {a^nb^kc^j | n,k,j >= 0} (бесконечный, слова соответствующие рег. выражению a*b*c*), контекстно-свободный: L = {a^mb^m | m > 0} - язык содержащий слова ab aabb aaabbb, т.е. язык соответствующий скобкам (если заменить a и b на ( и ). Язык L = {a^nb^nc^n | n > 0} - контекстно-зависимый. Регулярных выражений (и соответствующих конечных автоматов) для разбора последних двух (контекстно-свободных/зависимых) не существует.

Нужно заметить, что имплементации регэкспов имеют некоторые «костыли», которые позволяют немного выйти за рамки «регулярности», но ограниченно (грубо говоря до определённой длины слов)/

Исходная версия invy, 09.01.15 14:28:

Ты серьёзно?

Всё не так совершенно.

Не надо смешивать это с алфавитом.

Над алфавитом T = {a, b, c} можно построить все виды языков. Регулярный L = {abc} (конечный, одно слово abc), или L = {a^nb^kc^j} (бесконечный, слова соответствующие рег. выражению a*b*c*), контекстно-свободный: L = {a^mb^m} - язык содержащий слова ab aabb aaabbb, т.е. язык соответствующий скобкам (если заменить a и b на ( и ). Язык L = {a^nb^nc^n} - контекстно-зависимый. Регулярных выражений (и соответствующих конечных автоматов) для разбора последних двух (контекстно-свободных/зависимых) не существует.