Gramática regular

Prévia do material em texto

Gramática regular
Atividade
1) Gramática regular.
a) começar com aa.
S → aA
A→ aB
B → aA| bB| �
b) não começar com aa.
S → Aa| Ab
A→ Bb
B → Ba| Bb| �
c) terminar com bbb.
S → Sa| Sb| Ab
A→ Sa| Bb
B → Sa| Cb
C → �
d) não terminar com bbb.
S → Sa
S → Ab
A→ Ba
B → Ab
B → Ca
C → �
e) contar com a subcadeia aabbb.
S → Sa| Sb| Ab
A→ Bb
B → Cb
C → Db
D → Eb
E → Ea| Eb| �| a| b
f)não contar com a subcadeia aaa.
S → Aa| Bb| �
A→ Ca| Bb| �
C → Da| Bb| �
D → Da| Db
B → Bb| Aa| �
g) possuir comprimento maior ou igual
a 3.
S → Aa| Ab|
A→ Ba| Bb
B → Ca| Cb
C → Ca| Cb| �
h) possuir comprimento menor ou igual
a 3.
S → Aa| Ab| �
A→ Ba| Bb| �
B → Ca| Cb| �
C → Da| Db| �
D → Da| Db
i) possuir comprimento diferente a 3.
S → aA| bB
A→ aC| bD
B → aD| bB
C → aA| bB| �
D → aC| bD
j) possuir comprimento par.
S → aA| bA
A→ aB| bB
B → aA| bA| �
l) possuir comprimento ímpar.
S → aA| bA
A→ aB| bB| �
B → aA| bA
m) possuir comprimento múltiplo de 4.
S → aA| bA
A→ aB| bB
B → aC| bC
C → aD| bD
D → aA| bA| �
n) possuir quantidade par de a.
S → aA| bB
A→ aC| bD
B → aD| bB
C → aA| bB| �
D → aC| bD
o) possuir quantidade ímpar de b.
S → aA| bB
A→ aA| bB
B → aB| bC| �
C → aC| bB
1