Упражнения

1. В таблице 1 представлено множество S правил грамматики определяющей язык записи числа. Определите для этой грамматики V_Т, V_A, I.

2. В таблице 1 представлено множество S правил грамматики определяющей язык записи числа. Определите для этой грамматики эффективный циклический символ и укажите правило доказывающее это.

3. В таблице 1 представлено множество S правил грамматики определяющей язык записи числа. Определите тип этой грамматики. Обоснуйте ответ.

4. В таблице 1 представлено множество S правил грамматики определяющей язык записи числа. Запишите бинарные отношения для пар (П,Ф) и (М,Б).

5. Постройте синтаксическое дерево вывода числа -12,5е-7

6. Напишите линейно-скобочную запись числа +32.7е-23

7. Определите грамматику, порождающую язык определения идентификатора. V_Т={И,Б,Ц,’_’} где И - идентификатор, Б - буква, Ц - цифра, ’_’ - знак подчеркивания. Для определения идентификатора используйте правила языка Паскаль.

Автоматные грамматики.

 

FОпределение: 1) Правило вывода порождающей грамматики будем называть заключительным, если оно имеет вид А®х, где
А – нетерминальный символ, а х – терминальная цепочка.

2) Правило вывода порождающей грамматики называется праволинейным (леволинейным), если оно имеет вид А®хВ.

3) Не укорачивающую КС-грамматику называют праволинейной (леволинейной), если все ее правила праволинейны (леволинейны) или заключительны.

Лемма 5. По любой праволинейной грамматике может быть построена эквивалентная ей автоматная грамматика. По любой грамматике, включающей лишь правила вида А®å , а также праволинейные и заключительные правила, может быть построена почти эквивалентная автоматная грамматика.

Методы распознавания и анализа языков.