Atps Linguagem Formais E Automatos

Índice

Exercício 1.........................................................................................................................2
Exercício 2.........................................................................................................................2
Exercício 3.........................................................................................................................2
Exercício 4.........................................................................................................................3
Exercício 5.........................................................................................................................3
Exercício 6.........................................................................................................................3
Exercício 7.........................................................................................................................4
Exercício 8.........................................................................................................................4
Exercício 9.........................................................................................................................4
Exercício 10.......................................................................................................................5
1-) Cadeias que não iniciam com “aa”.

S  a
S  abX
S  bX
S  cX
X  aX
X  bX
X  cX
X  

2-)Cadeias terminando com 3 símbolos “b” consecutivos.

S→ xbbb x→ ax x→ bx x→ cx x→ ɛ

3-) Cadeias iniciando com “a” e terminando com “c”.

S→ axc x→ ax x→ bx x→ cx x→ ɛ

4-)Cadeias que iniciam com “a” e não terminam com “c”.

S→ axa
S→ axb x→ ax x→ bx x→ cx x→ ɛ

5-)Cadeias que não iniciam com “a” e que terminam com “c”.

S→ bxc
S→ cxc
S→ c x→ ax x→ bx x→ cx x→ ɛ

6-)Cadeias que não iniciam com “a” e não terminam com “c”.

S  XYZ
X  b
X  c
Y  bY
Y  aY
Y  
Y  cY
Z  a
Z  b

7-) Cadeias com exatamente 3 símbolos “b”.

S 