Автор Тема: вопрос по теории формальных языков.  (Прочитано 1708 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Voigosh

  • Пользователь
  • **
  • Сообщений: 34
    • Просмотр профиля
у меня есть лемма  по материалу из изложенного курса.
Задача в том, что нужно более подробно изложить их доказательство. вот что  я представила.
Определение
Пусть 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 будет приписана всем символам, из которых за один шаг достижимы лишь сводимые с ними символы и символы, которым уже приписана высота на предыдущих  шагах.
Пусть 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''ϵD(R), следует : R-> x'R''y', R''-> xR'y т.к. R' ϵ Q\D(R), а R'' ϵD(R),то мы никогда не сможем вернуться обратно к символу R(следует из определения).
Как это следует из определений?
Следовательно, высота h(R') ≠|Q|, и поэтому max(h(R')+1,R' ϵU) ≤ |Q|∎
Высотой рассматриваемой грамматики G, в записи h(G), будем называть max{ h(R)| R∈Q}.
Высотой КС-языка L будем называть минимальную высоту КС-грамматики, задающей этот язык L.
Заметим, что два нетерминала одинаковой высоты не обязаны быть сводимы.

  Какой можно  привести пример КС-грамматик, у которых есть нетерминалы одинаковой высоты как сводимые, так и несводимые?
 вот то что выделено,могли бы с этим помочь?

 

Люди помогите решить задачу по теории вероятностей.очень прошу...

Автор sancho199268

Ответов: 0
Просмотров: 1900
Последний ответ 27 Мая 2011, 14:27:30
от sancho199268
Ребят помогите решить парочку задач по теории вероятности

Автор erta

Ответов: 1
Просмотров: 3642
Последний ответ 08 Декабря 2009, 00:06:26
от Kirpich
Помогите решить задачу по теории вероятностей! Завтра зачет !

Автор EnigmA

Ответов: 5
Просмотров: 2692
Последний ответ 20 Декабря 2009, 18:11:46
от Asix
Помогите решить задачу по теории веротяности (определение ошибки)

Автор Верона

Ответов: 2
Просмотров: 2371
Последний ответ 18 Декабря 2009, 18:33:57
от Asix
Помогите решить задачу по теории вероятности (закон распределения ...)

Автор Eminka

Ответов: 1
Просмотров: 3685
Последний ответ 18 Декабря 2009, 21:03:09
от Kirpich