Теорема Огдена. Лемма о разрастании КС-языков

Лемма позволяет определить является ли язык контекстно-свободным. Она дает необходимое условие, но не достаточное условие того, что язык является контекстно-свободным, то есть при наличии удовлетворяющих лемме условий язык не обязательно является контекстно-свободным.

Лемма: Пусть язык является КС-языком, тогда существует такое число - целое и положительное, для которого можно выделить цепочку , причем длина, которой не меньше, чем и которую можно представить в следующем виде

,

где

;

.

Тогда вновь получаемая цепочка , будет иметь вид

, ,

также будет принадлежать исходному языку .

Пример: Проверить необходимое условие для языка

.

Решение:

, ;

;

;

;

;

;

;

: ;

: ;

: ;

;

: ;

Данный язык удовлетворяет условиям теоремы Огдена.

Пример: Проверить необходимое условие для языка

;

Решение:

Пусть . Тогда . Так как , то в цепочке не могут быть вхождения каждого из символов , и . Таким образом цепочка , которая по лемме о разрастании КС-языков принадлежит , содержит либо символов , либо символов . Но она не может иметь вхождений каждого из символов , и , потому что . Значит вхождений какого-то из символов в больше, чем другого, и, следовательно, . Полученное противоречие позволяет заключить, что - не КС-язык.

Пример: Проверить необходимое условие для языка

;

.

Решение:

;

;

;

;

;

Данный язык удовлетворяет условиям теоремы Огдена, но не является контекстно-свободным.

Домашнее задание: Написать грамматику типа 2 и грамматику типа 1 для языка .

Домашнее задание: Проверить равенства

1.

.

2.

.

Дата добавления: 2014-01-07