[flame19]

Добрый день всем!

Большая просьба помочь с курсовой по предмету "Теория автоматов и формальных языков" тема курсовой "Индекс грамматики и языка". Преподавателю (Тайцлин М.А. - можешь слышали) курсовая, как ни странно, не понравилась из-за объема. И он сказал взять отдельную теорему из работы и по-своему её доказать.

Вот инфо:

Теорема.
Путь G=/A, Q, S, P/ КС-грамматика без самовставления. Тогда L(G) конечен.

Определения.
Высотой рассматриваемой грамматики G, в записи h(G), будем называть max{ h(R)| R принадлежит Q}. Высотой КС-языка L будем называть минимальную высоту КС-грамматики, задающей этот язык L.
Заметим, что два нетерминала одинаковой высоты не должны быть сводимы.


ТЕКСТ ДОКАЗАТЕЛЬСТВА, КОТОРОЕ ПРЕПОДАВАТЕЛЮ НЕ НРАВИТСЯ:


СПАСИБО ЗА ЛЮБУЮ ПОМОЩЬ!!!

@темы: Математическая логика, Теория графов, Дискретная математика

Comments

[Вилл в носочках]

Вопросы пока просто по терминам:
1) что такое h(R) для R из Q?
2) приведенная грамматика, это грамматика в форме Хомского?

[All_ex]

Тут вспомнилось...
"-Алло, здравствуйте! Вас беспокоит Робинович по поводу объявления об учителе игры на фортепиано и тромбоне для ребёнка...
-Да, Вы играете на фортепиано и тромбоне?...
-Нет, я хотел сказать, чтобы Вы на меня не рассчитывали...!"
flame19 извините, вырвалось...

[flame19]

Вилл в носочках, h(R) - высота символа R. По определению: Высота символа
Пусть RϵQ.
1). Высота R есть 1 (в записи h(R)= 1) тогда и только тогда , когда для произвольного R’∈ Q, из того, что для произвольного R’∈ Q, из того, что существует такие x,y ∈ (A∪Q)*, что R→xR’y∈P, следует, что R и R’ сводимы.
2). Пусть условие 1) настоящего определения не выполнимы для R.
Рассмотрим множество
U = { R’ | R’∈(Q\D(R)); R”∈ D(R); x,y∈ (A∪Q)*; R”→xR’y∈ P}.
Положим
h(R)= max{h(R’)+1| R’∈ U}.

[flame19]

Теорема.
Путь G= КС-грамматика без самовставления.
Тогда L(G) конечен.
Доказательство. Если L(G) = ∅, то теорема доказана.
Без ограничения общности можно считать, что G приведенная.
Докажем индукцией по высоте G, что L(G) конечен.
Базис индукции. Пусть h(G)=1.
Если L(G)= {e}, где e пустое слово, то теорема доказана.
Так как G- приведенная грамматика без самовставления, то ясно, что для произвольного R∈Q и произвольного правила R→α ∈P либо α∈ Q, либо α ∈A^*.
«Почему вот это верно? »
Заметим, что так как h(G)=1,то если для R,R’∈Q правило R→R’∈P, то R и R’ сводимы, то есть R’∈D(R).
Ясно, что из приведенности G следует, что S∈D(R).
Рассмотрим в качестве P* множество правил, в которых всякое вхождение всякого нетерминала R ∈Q заменено на S, после чего правило S →S выброшено, если оно было. Ясно, что в грамматике G*= , эквивалентной G, правая часть всякого правила пуста или состоит из терминалов. СледовательноL(G)=L(G*) конечный язык.
«Почему грамматика G* эквивалентна G?»
вот в чем вопрос?

[Вилл в носочках]

R∈Q и произвольного правила R→α ∈P либо α∈ Q, либо α ∈A*.
Потому что высота R по предположению индукции у нас =1, а самосводимости нет.
Более подробно:
приведенная грамматика => в ней нет бесполезных символов. А значит из любого нетерминала за конечное число шагов можно получить слово, состоящее из одних только терминалов.

предположим противное, пусть у нас есть правило вида R->xR'y (x,y∈(A∪Q)*).
Тогда, так как известно, что h(R)=1 следовательно R и R' сводимы, то есть существуют такие x' и y' ∈A* что R'=>x'Ry' (выводимо в грамматике G).
Тогда имеем: R->xR'y (правило), R'=>x'Ry'(выводимо), значит R=>xx'Ry'y => x''Ry'', где x'', y'' уже принадлежат A* (то есть мы взяли xx' и y'y, и все нетерминалы, которые в них содержались, свели к словам из терминалов, т.к. бесполезных символов в нашей грамматике нет), то есть R самовставим, что противоречит условию.

[Вилл в носочках]

2)Почему грамматика G* эквивалентна G?

Грамматики эквивалентны, если языки, которые они порождают, эквивалентны.
По доказанному ранее, произвольное правило из P выглядит либо “A->B”, либо “A->w” (w – цепочка терминалов). Так как по предположению индукции h(G)=1 =max{h(A)| A принадлежит Q}, значит h(A)=1 для любого A из Q.
Если у нас есть правило A->B, то из того что h(A)=1 следует, что A и В сводимы. При этом h(B) тоже =1, и получается, у нас есть правило B->A.
Таким образом, любое терминальное слово, которое выводится из A, будет выводиться из B. Это верно для всех сводимых нетерминалов. То есть один из нетерминалов А или B можно просто выкинуть. Поэтому теперь вместо всех сводимых нетерминалов мы оставляем только S. В грамматике с правилами P* выводятся все те же слова, что и в исходной грамматике. То есть G и G* эквивалентны.

[flame19]

G- приведенная грамматика без цепных правил.
Индукция по числу правил:
Базис:
|P|=1;
S→α α∈A*(иначе S будет бесполезным символом, что противоречит условию)
Для |P|≤n доказано;
Докажем для
|P|= n+1;
R→α∈P α∈(A∪Q)*
Индукция по числу нетермин. k в α:
Базис:
k=1.
R→xBy B∈Q
Тогда по индукционному предположению для B существует конечное число выводов(т.к число правил конечно и нет самовставлений)
видя: B→B1→B2→…. γ∈A*
B1,B2,…∈Q
Тогда символ B можно заменить на все возможные γ и получается
R→x γ1 y, R→x γ2 y,… R→x γk y
k≤c- доказано, k= c+1.
Заменим новое правило в виде
R→x1 x2, x1 x2∈(A∪Q)*
В x1 - С нетерминалов, в x2 – 1 нетерминал
Удалим правило R1→ R2 R3
R2→x1
R3→x2
Тогда по инд. Предположению
R2→x1 R3→x2 можно переделать в правила вида R2→γ1 R3→γ2, γ1,γ2∈ A*
Тогда
R1→ R2 R3 можно заменить на R1→ γ1,γ2∈ A*
Ч.т.д
а к первому в этом есть смысл?

[Вилл в носочках]

эээ само индукционное предположение было о чем? всмысле, что вы тут доказывали?

[Вилл в носочках]

Вот еще, на всякий случай. Важно различать A->x правило (то есть в P это прямо прописано) и A=>x (то есть пользуясь цепочкой правил можно вывести из A x).
И второе, когда вы говорите, что меняете одно правило на другое - это значит, вы строите некоторою новую (возможно эквивалентную) грамматику. Дальнейшие ваши рассуждения уже относятся к эквивалентной грамматике, но не к вашей исходной. И то, что в эквивалентной грамматике будут правила какого-либо вида, совсем не означает то, что в исходной они такие же.

[flame19]

простите ,я тут всё перепутала, завтра с этим подробно разбирусь,я не так переписала,а сейчас уже мало понимаю и целый день с этим. спасибо Вам!)) огромное.