Специальная математика. Соловьев А.Е. - 78 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

автомате осуществлялись переходы. Заметим, что пустые клеточки дают состояние - пустое
множество.
A aB | bB | aC
B bC | b
C a
B
a,b b
A b F
a a
C
7.8. Переход от праволинейной грамматики к автоматной
Праволинейная грамматика - грамматика с правилами вида:
A
A В
где A, B V
N
,  V
*
T
То есть это такая КС-грамматика, где вначале идет любое количество терминальных
символов, а в конце возможен один нетерминальный символ
Пример:
Дана праволинейная грамматика:
1. SaA
2. Sbc
3. SA
4. AabbS
5. AcA
6. AE
Правила 2, 3, 4 – нарушают требования к автоматным грамматикам.
Их можно последовательно заменить совокупностями автоматных правил.
— 78 —
A B C F
a B,C F
b B C,F
{A} {B,C} {B} {F} {CF} {}
a {B,C} {F} {} {} {F} {}
b {B} {C,F} {C,F} {} {} {}
4a Aa<bbS>
4b <bbS>b<bS> правило 4.
4c <bS>bS
{ }
автомате осуществлялись переходы. Заметим, что пустые клеточки дают состояние - пустое
множество.


                                          A    B      C      F   A  aB | bB | aC
                                 a       B,C          F          B  bC | b
                                 b        B    C,F               Ca

                                            {A}      {B,C}    {B}    {F}   {CF}     {}
                                     a     {B,C}      {F}      {}     {}    {F}     {}
                                     b      {B}      {C,F}   {C,F}    {}     {}     {}



                   B
         a,b                b

     A                b              F

         a                   a
                  C

             7.8. Переход от праволинейной грамматики к автоматной

  Праволинейная грамматика - грамматика с правилами вида:
A
A  В
 где A, B  VN ,  V*T
То есть это такая КС-грамматика, где вначале идет любое количество терминальных
символов, а в конце возможен один нетерминальный символ

Пример:
Дана праволинейная грамматика:
1. SaA
2. Sbc
3. SA
4. AabbS
5. AcA
6. AE
Правила 2, 3, 4 – нарушают требования к автоматным грамматикам.
Их можно последовательно заменить совокупностями автоматных правил.



{                      }
    4a Aa
    4b b         правило 4.
    4c bS




                                               — 78 —

Страницы