Здравствуйте!
Могли бы помочь с примером. Разбираюсь в теме "Индекс грамматики и языка" по предмету Теория формальных языков.
Тема как я понимаю,в близко рассматривается в нашем университете. Так что представлю лемму по этому курсу.
Определение. Высота символа
Пусть 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}.
Лемма.
Определение высоты символа корректно определяет высоту всякого R∈Q. Высота произвольного символа R∈Q не превосходим |Q|.
Доказательство.
Фактически в определении прямо описан способ вычисления высоты символа. При этом сначала высота 1 будет приписана всем символам, из которых за один шаг достижимы лишь сводимые с ними символы и символы, которым уже приписана высота на предыдущих шагах.
Высотой рассматриваемой грамматики G, в записи h(G), будем называть max{ h(R)| R∈ Q}. Высотой КС-языка L будем называть минимальную высоту КС-грамматики, задающей этот язык L.
Заметим, что два нетерминала одинаковой высоты не обязаны быть сводимы.
так вот вопрос, нужно представить примеры КС-грамматик, у которых есть нетерминалы одинаковой высоты как сводимые, так и несводимые.
могли бы с этим помочь разобраться?
Заранее спасибо.
Могли бы помочь с примером. Разбираюсь в теме "Индекс грамматики и языка" по предмету Теория формальных языков.
Тема как я понимаю,в близко рассматривается в нашем университете. Так что представлю лемму по этому курсу.
Определение. Высота символа
Пусть 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}.
Лемма.
Определение высоты символа корректно определяет высоту всякого R∈Q. Высота произвольного символа R∈Q не превосходим |Q|.
Доказательство.
Фактически в определении прямо описан способ вычисления высоты символа. При этом сначала высота 1 будет приписана всем символам, из которых за один шаг достижимы лишь сводимые с ними символы и символы, которым уже приписана высота на предыдущих шагах.
Высотой рассматриваемой грамматики G, в записи h(G), будем называть max{ h(R)| R∈ Q}. Высотой КС-языка L будем называть минимальную высоту КС-грамматики, задающей этот язык L.
Заметим, что два нетерминала одинаковой высоты не обязаны быть сводимы.
так вот вопрос, нужно представить примеры КС-грамматик, у которых есть нетерминалы одинаковой высоты как сводимые, так и несводимые.
могли бы с этим помочь разобраться?
Заранее спасибо.
