Классификация языков по Хомскому; порождающие грамматики.
Классификация грамматик по Хомскому основывается на ограничениях, накладываемых на продукции , т.е. ограничения на виды цепочек, обозначенных как
и
.
В приводимой в табл.3.1 классификации грамматик по Хомскому разные грамматики отнесены к одному типу на том основании, что они порождают один класс языков. Так, например, грамматики типа 3, называемые праволинейными, регулярными, автоматными – это разные грамматики, но порождаю один класс языков. Один класс в том смысле, что любой язык, порождаемый одной из перечисленных грамматик, может быть порожден и любой другой.
Таблица 3.1
Названия грамматики | Ограничения на правила (на продукции) |
Тип 0 (или общего вида, или без ограничений) | Нет никаких ограничений на ![]() ![]() |
Тип 1 (контекстно-зависимая (КЗ); неукорачивающая; непосредственных составляющих (НС) ) | Ограничения только на длины цепочек ![]() ![]() ![]() ![]() |
Тип 2 (контекстно-свободная (КС); безконтекстная) | Каждая продукция имеет вид: ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Тип 3 (праволинейная или правостороняя; леволинейная или левосторонняя; регулярная; автоматная ) | Каждая продукция имеет вид: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
В правосторонней (праволинейной) грамматике цепочки удлиняются только вправо, а продукции имеют вид , где
- цепочка терминалов. В левосторонней (леволинейной) грамматике цепочки удлиняются только влево, а продукции имеют вид
, где
- цепочка терминалов. Автоматная грамматика представляет собой частный случай правосторонней или левосторонней грамматики, в которой цепочка терминалов упростилась до одного символа. Таким образом, в автоматной грамматике продукции имеют вид
или
, где
- это цепочка из одного символа. Причем, если
, то
не встречается в правых частях правил. Для любой праволинейной грамматики
можно построить эквивалентную ей автоматную
. Эквивалентную в том смысле, что языки, порождаемые грамматиками
и
, будут совпадать.
Продукция, т.е. правило, вида обычно называется
- продукциейили
- правилом.
Подчеркнем, что КС грамматика, содержащая - правила, не является грамматикой НС.
Из сравнения грамматик видно, что
n грамматика типа 3 является частным случаем грамматики типа 2;
n грамматика типа 2 является частным случаем грамматики типа 1, если не содержит - продукций;
n грамматика типа 1 – частный случай грамматики типа 0.
Будем считать, что если язык порождается грамматикойтипа
, то
называется языкомтипа
.
Следует отметить, что если язык задан какой-то грамматикой, то это еще не значит, что его нельзя породить менее мощной грамматикой. Например, КС-грамматика с продукциями порождает язык {0,1}*. Этот же язык можно породить менее мощной грамматикой: праволинейной с продукциями
или леволинейной с продукциями
.
Дата добавления: 2015-08-11; просмотров: 866;