конспекты занятий по курсу

«Теория и реализация языков программирования»

 

Занятие 6

 

 

 

(<<<) предыдущий

наверх

следующий (>>>)

 

 

6. Контекстно-свободные языки (продолжение)

6.2. Преобразование МПА-КСГ

Алгоритм преобразования описан в [1] без подробного примера его применения (на увеличение объёма печатного издания всегда имеются некоторые ограничения), в связи с чем у отдельных учащихся возникают сложности с пониманием алгоритма. Поэтому пример для простого случая приводим ниже.

 

 

 

 

 

Пример 6.2. Преобразование МПА-КСГ

Переход от МП автомата к КС-грамматике.

Рассмотрим МПА, соответствующий языку :

В соответствии с условиями теоремы о переходе от МПА к КСГ правила последней имеют следующий вид (запишем сначала их обобщённо, затем подробно):

Или, подставляя все значения i:

   и

* * *

Далее (при записи непустой цепочки в магазин):

Для функции перехода  это будет

Или, подставляя все значения i и  j:

* * *

Для функции перехода  это будет

Или, подставляя все значения i и  j:

* * *

Наконец, для функций перехода, которые записывают пустую цепочку в магазин:

 

 

Для

Для

Для

-          

-          

-          

 

 

 

Переобозначим полученные вспомогательные знаки в КСГ более кратко.

 

 

 

До переобозначения

После переобозначения

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Или, более плотно:

Полученная грамматика оказалась неприведённой (например, знаки Е и H никуда не сводятся). После приведения грамматики число её правил заметно сократится:

Опробуем её на примере:

или

.

 

Задача 6.1. Измените МПА так, чтобы он принимал данный язык, начиная с n = 0 (т.е. и пустую цепочку) и самостоятельно перейдите от него к КСГ.

 

 

 

Совет. Познакомьтесь с описанием соответствующих алгоритмов в пособии [1] и введёнными при этом понятиями и обозначениями.

 

== Ссылки ==

[1] Серебряков В.А. [и др.]. Теория и реализация языков программирования. М.: МЗ-Пресс, 2003 (1-е изд.) и 2006 (2-е изд). – 294 c. (681.3/ Т33).

 

 

 

 

(<<<) предыдущий

наверх

следующий (>>>)