Задания по формальным языкам

1. Для правила грамматики выполнить следующие задания.

a) Описать все четыре компоненты грамматики (множество терминальных символов, множество нетерминальных символов, множество правил, начальный символ).

b) Построить последовательность вывода цепочки, сложность которой должна быть не менее 10 символов, а каждое правило использовалось не менее одного раза.

c) Построить дерево вывода цепочки.

d) Определить какому типу по Хомскому принадлежит грамматика.

S→aSb S→aSS S→c

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

S→aA A→aA|b|cC B→a|cB C→bAC

3. Построить грамматику для оператора цикла с предусловием.