ПРАВОЛИНЕЙНАЯ ГРАММАТИКА

Праволинейная грамматика – грамматика, в которой правая часть каждого правила содержит не более одного терминального символа.

Преобразование в праволинейную грамматику:

Пример 1	Пример 2

Задана грамматика:

1. <S>a<A>
2. <S>bc
3. <S><A>
4. <A>abb<S>
5. <A>c<A>
6. <A>ε

Задача: построить автомат.

2,3,4 правила нуждаются в преобразовании.

2. . Обозначение «ε» тут несущественно. Можно записать любой символ.

4.

3. - здесь просто переписываем все случаи чему равно <A>

В результате получаем следующую грамматику:

1. <S>a<B>
2. <S>b<cε>
3. <cε>c<ε>
4. <ε>ε
5. <S>a<bbS>
6. <bbS>b<bS>
7. <bS>b<S>
8. <S>c<A>
9. <S>ε
10. <A>a<bbS>
11. <A>c<A>
12. <A>ε

Что можно записать следующей таблицей:

	a	b	c
<S>	<A>,<bbS> - недетерминированность	<cε>	<A>	допустимо
<cε>	-	-	<ε>	-
<ε>	-	-	-	допустимо
<bbS>	-	<bs>	-	-
<A>	<bbS>	-	<A>	допустимо
<bs>	-	<S>	-	-