Практическое занятие 2. Построение дерева синтаксического разбора, левого и правого выводов цепочек.

Цель: освоение навыка построения дерева синтаксического разбора, левого и правого выводов цепочек, определения однозначности грамматики.

Задание 1.

Какие из приведенных ниже цепочек можно вывести в данной грамматике с начальным нетерминалом <S>?

<S> → a <A> c <B>

<S> → <B> d <S>

<A> → <B> a <B>

<A> → a <B> c

<A> → a

<A> → b

<B> → a <S> c <A>

<B> → c <A> <B>

1. aacb

2. aababcbadcd

3. aacbccb

4. aacabcbcccaacdca

Рекомендуемая литература: [1], [2], конспект лекций.

Этапы выполнения.

Для каждой цепочки:

1. Построить дерево синтаксического разбора.

2. Построить левый вывод.

3. Построить правый вывод.

4. Сделать вывод о выводимости цепочки в данной грамматике.

Задание 2.

Покажите, что следующая грамматика неоднозначна:

<S> → b <A>

<S> → a <B>

<A> → a <S>

<A> → b <A> <A>

<A> → a

<B> → b <S>

<B> → a <B> <B>

<B> → b

Покажите, что грамматика, имеющая продукции вида

<S> → b <A>

<S> → a <B>

<S> → b <A> <S>

<S> → a <B> <S>

<A> → b <A> <A>

<A> → a

<B> → a <B> <B>

<B> → b

есть однозначная грамматика, порождающая тот же язык.

Рекомендуемая литература: [1], [2], конспект лекций.

Этапы выполнения.

1. Подобрать один-два примера цепочек, порождаемых первой грамматикой, подтвердив этот факт построением их вывода в данной грамматике.

2. Построить дерево синтаксического разбора для каждой цепочки.

3. Проанализировать возможность построения еще одного дерева для той же цепочки. Сделать соответствующий вывод.

4. Выполнить такие же действия для второй грамматики. Сделать вывод.

5. Провести анализ и сделать вывод о том, что обе грамматики порождают один и тот же язык.

Практическое занятие 3. Эквивалентные преобразования кс-грамматик.

Цель: освоение навыка выполнения эквивалентных преобразований КС-грамматик с целью оптимизации их дальнейшего использования.

Задание 1.

Найти лишние нетерминалы в следующей грамматике с начальным нетерминалом <S>:

<S> → a <A> <B> <C> <S> → b <C> <E> <S> <S> → a <E> <A> → b <E> <A> → <S> <C> <D> <A> → d <B> → d <F> <S> <B> → a <B> <C>

<C> → a <E> <S> <C> → b <E> <D> → a <A> <C> <D> → d <E> → a <C> <E> <E> →  <F> → <A> <B> <F> → a <F>

Рекомендуемая литература: [1], [2], конспект лекций.

Этапы выполнения.

1. Определить множество непродуктивных нетерминалов.

2. Исключить из общего списка правила, содержащие нетерминалы, попавшие в множество непродуктивных.

3. Определить множество недостижимых нетерминалов.

4. Исключить из общего списка правила, содержащие нетерминалы, попавшие в множество недостижимых.

5. Записать окончательный набор правил, полученный после проведенных преобразований.

Задание 2.

Преобразовать данные грамматики с начальным нетерминалом <S>, исключив из нее -правила:

<S> → a <S> b <S> <S> → b <S> a <S> <S> → 

<S> → <S><S> <S> → 1 <A> 0 <A> → 1 <A> 0 <A> → 

Рекомендуемая литература: [1], [2], конспект лекций.

Этапы выполнения.

Для каждой грамматики:

1. Применить алгоритм преобразования грамматики с целью исключения -правил.

2. Записать окончательный набор правил, полученный после проведенных преобразований.

Задание 3.

Преобразовать данные грамматики с начальным нетерминалом <S> к нормальной форме Хомского:

<S> → 1 0 <S> 0 <S> → a <A> <A> → b <A> <A> → a

<S> → <S><S> <S> → 1 <A> 0 <A> → 1 <A> 0 <A> → 

Рекомендуемая литература: [1], [2], конспект лекций.

Этапы выполнения.

Для каждой грамматики:

1. Применить алгоритм преобразования грамматики к нормальной форме Хомского.

2. Записать окончательный набор правил, полученный после проведенных преобразований.

Тема. Распознаватели и преобразователи: конечные автоматы и преобразователи.

Способы задания. Минимизация конечного автомата. Автоматные грамматики и конечные автоматы. Недетерминированные и детерминированные конечные автоматы.