ВУЗ:
Составители:
1) Язык L является рекурсивно перечислимым тогда и только тогда, когда он
определяется некоторой машиной Тьюринга.
2) Язык
L является контекстно- свободным (контекстно- независимым) тогда и только
тогда, когда он определяется автоматом с магазинной памятью.
3) Язык
L является автоматом (левосторонним или правосторонним), если он
определяется конечным автоматом.
Заметим, что хотя им и не определили этого специально, язык является контекстно
– зависимым (КС-языком) тогда и только тогда, когда он определяется так называемым
недетерминированным линейно ограниченным автоматом. Такой автомат представляет
собой недетерминированную машину Тьюринга, на которую наложено дополнительное
ограничение, которое заключается в том, что в процессе работы не должна увеличиваться
длина рабочей цепочки.
Мы показали, что в общем случае проблема остановки машины Тьюринга
алгоритмически неразрешима. Из этого вытекает, что такие свойства языков,
определяемых машиной Тьюринга, как распознаваемость, эквивалентность слов, пустота
пересечения, бесконечность и ряд других, которые связаны в
конечном счете с этой
проблемой, также алгоритмически неразрешимы. Указанные свойства распространяются и
на линейно ограниченные автоматы, а значит, и на НС-языки.
Что касается проблемы остановки для МПА и КА, то для них она разрешима,
поскольку множества слов, порождаемых КС- и А- грамматиками, являются
рекурсивными множествами. Поэтому для КС- и
А- языков алгоритмически разрешима
проблема пустоты, конечности и бесконечности ,распознаваемости принадлежности
произвольного слова к языку и проблема эквивалентности слов языка. В то же время и для
КС- языков существует алгоритмически неразрешимые проблемы. Это прежде всего
проблемы, связанные с пересечением КС-языков, также как не пустоты пересечения,
автоматности пересечения и контекстной свободности
пересечения, а также проблемы,
связанные с неоднозначностью вывода в КС-языках. Иерархия автоматов и
соответствующих им формальных языков показана на рис.3.11. Очевидно, что каждый из
автоматов определенного уровня иерархии, кроме указанного соответствующего класса
языков, распознаёт также все языки более низкого уровня иерархии, разумеется
естественно, если проблема распознавания для данного языка
разрешима. В этом смысле
автоматы с магазинной памятью распознают КС- и А-языки, а машина Тьюринга- все
перечисленные типы
языков.
Рис.3.11
алгоритмы Формальные языки
Машина Тьюринга
Линейно ограниченные
автоматы
Автоматы с магазинной
памятью
Конечные автоматы
Рекурсивные
пересчислимые языки
Языки непосредственных
составляющих(контексно
зависимые языки)
Контестно свободные
языки
Автоматные языки
Страницы
- « первая
- ‹ предыдущая
- …
- 69
- 70
- 71
- 72
- 73
- …
- следующая ›
- последняя »
