Reverso de uma Linguagem Regular
1
Teorema:
R
reverso L de uma linguagem regular
é uma linguagem regular
L
Idéia da prova:
Construa um NFA que aceita
R
L
:
inverta as transições do NFA
que aceita L
2
Prova
Como L é regular,
existe um NFA que aceita
L
Exemplo:
b
L  ab * ba
a
b
a
3
Inverta as Transições
b
a
b
a
4
Torne o antigo estado inicial
o estado final
b
a
b
a
5
Adicione um novo estado inicial
b

a
b

a
6
A máquina resultante aceita
R
L
R
L
é regular
L  ab * ba
b
L  b * a  ab
R

a
b

a
7
Gramáticas
8
Gramáticas
Gramáticas expressam linguagens
Exemplo:
Inglês
sentence  noun _ phrase
noun _ phrase  article
predicate  verb
predicate
noun
9
article  a
article  the
noun  boy
noun  dog
verb  runs
verb  walks
10
Uma derivação de “the boy walks”:
sentence  noun _ phrase
predicate
 noun _ phrase
verb
 article
verb
noun
 the noun
verb
 the boy verb
 the boy walks
11
Uma derivação de “a dog runs”:
sentence  noun _ phrase
predicate
 noun _ phrase
verb
 article
noun
verb
 a noun
verb
 a dog verb
 a dog runs
12
Linguagem da gramática:
L = { “a boy runs”,
“a boy walks”,
“the boy runs”,
“the boy walks”,
“a dog runs”,
“a dog walks”,
“the dog runs”,
“the dog walks” }
13
Notação
noun  boy
noun  dog
Variável
ou
Não terminal
Regra de
Produção
Terminal
14
Outro Exemplo
Gramática:
S  aSb
S 
Derivação da sentença
ab:
S  aSb  ab
S  aSb
S 
15
Gramática:
S  aSb
S 
Derivação da sentença
aabb:
S  aSb  aaSbb  aabb
S  aSb
S 
16
Outras derivações:
S  aSb  aaSbb  aaaSbbb  aaabbb
S  aSb  aaSbb  aaaSbbb
 aaaaSbbbb  aaaabbbb
17
Linguagem da gramática
S  aSb
S 
L  {a b : n  0}
n n
18
Mais Notação
Gramática
G = (V, S, S, P)
V : Conjunto de variáveis
S:
Conjunto de símbolos terminais
S : Variável inicial
P:
Conjunto de regras de produção
19
Exemplo
Gramática
G : S  aSb
S 
G  V ,T , S , P 
V  {S}
T  {a, b}
P  {S  aSb, S  }
20
Mais Notação
Forma Sentencial:
Uma sentença que contém
variáveis e terminais
Exemplo:
S  aSb  aaSbb  aaaSbbb  aaabbb
forma sentencial
sentença
21
Escrevemos:
*
S  aaabbb
Como abreviação de:
S  aSb  aaSbb  aaaSbbb  aaabbb
22
De modo geral:
Se:
*
w1  wn
w1  w2  w3    wn
23
Por default:
*
w  w
24
Exemplo
Gramática
S  aSb
S 
Derivações
*
S 
*
S  ab
*
S  aabb
*
S  aaabbb
25
Exemplo
Gramática
S  aSb
S 

Derivações
S  aaSbb

aaSbb  aaaaaSbbbbb
26
Outro Exemplo de Gramática
Gramática G : S  Ab
A  aAb
A
Derivações:
S Þ Ab Þ b
S Þ Ab Þ aAbb Þ abb
S Þ Ab Þ aAbb Þ aaAbbb Þ aabbb
27
Mais Derivações
S  Ab  aAbb  aaAbbb  aaaAbbbb
 aaaaAbbbbb  aaaabbbbb

S  aaaabbbbb

S  aaaaaabbbbbbb

S a b b
n n
28
Linguagem de uma Gramática
Para uma gramática
com variável inicial
G
S:

L(G )  {w : S  w}
String de terminais
29
Exemplo
Gramática
S  Ab
G:
A  aAb
A
L(G) = {a b
n n+1
Já que:

: n ³ 0}
S a b b
n n
30
Uma Notação Conveniente
A  aAb
A
article  a
article  the
A  aAb | 
article  a | the
31
Gramáticas Lineares
32
Gramáticas Lineares
Gramáticas com no máximo uma variável do
lado direito de cada produção
Exemplos:
S  aSb
S  Ab
S 
A  aAb
A
33
Uma Gramática Não-Linear
Gramática
G:
S  SS
S 
S  aSb
S  bSa
L(G)  {w : na (w)  nb (w)}
34
Outra Gramática Linear
Gramática
G:
SA
A  aB | 
B  Ab
L(G )  {a b : n  0}
n n
35
Gramática Linear à Direita
Todas as produções têm a forma:
A  xB
ou
A x
Exemplo:
S  abS
S a
36
Gramática Linear à Esquerda
Todas as produções têm a forma:
A  Bx
ou
A x
Exemplo:
S  Aab
A  Aab | B
Ba
37
Gramáticas Regulares
38
Gramáticas Regulares
Uma gramática regular é qualquer
gramática linear à direita ou à esquerda
Exemplos:
G1
G2
S  abS
S  Aab
S a
A  Aab | B
Ba
39
Observação
Gramáticas regulares geram
linguagens regulares
Exemplos:
G2
G1
S  Aab
S  abS
A  Aab | B
S a
Ba
L(G1)  (ab) * a
+
L(G2 ) = a(ab)
40
Gramáticas Regulares
Geram
Linguagens Regulares
41
Teorema
Linguagens
Geradas por
Gramáticas Regulares

Linguagens
Regulares
42
Teorema - Parte 1
Linguagens
Geradas por
Gramáticas Regulares

Linguagens
Regulares
Toda gramática regular gera
uma linguagem regular
43
Teorema - Parte 2
Linguagens
Geradas por
Gramáticas Regulares

Linguagens
Regulares
Toda linguagem regular é gerada
por uma gramática regular
44
Prova – Parte 1
Linguagens
Geradas por
Gramáticas Regulares

Linguagens
egulares
A linguagem L(G ) gerada por
umq gramática regular G é regular
45
O caso de Gramáticas Lineares à Direita
Seja
G uma gramática linear à direita
Vamos provar :
L(G ) é regular
Idéia da Prova:
Vamos construir um NFA
com L( M )  L(G )
M
46
Gramática
Exemplo:
G é linear à direita
S  aA | B
A  aa B
Bb B|a
47
Construa o NFA M tal que
todo estado é uma variável da gramática:
A
S
S  aA | B
A  aa B
Bb B|a
VF
B
estado
final
especial
48
Adicione arcos para cada produção:
a
A
S
VF
B
S  aA
49
a
S
A
VF

B
S  aA | B
50
A
a
a
S
a

VF
B
S  aA | B
A  aa B
51
A
a
a
S
S  aA | B
A  aa B
B  bB
VF
a

B
b
52
A
a
a
S
S  aA | B
A  aa B
B  bB | a
a

VF
a
B
b
53
A
a
a
S
a

VF
a
B
b
S  aA  aaaB  aaabB  aaaba
54
NFA
Gramática
M
a
G
S  aA | B
a
B  bB | a
A
a
S

A  aa B
VF
a
B
b
L( M )  L(G ) 
aaab * a  b * a
55
Em Geral
Dada uma gramática linear à direita
G
com variáveis
V0 ,V1,V2,… ,Vn
e produções:
Vi  a1a2 amV j
ou
Vi  a1a2 am
56
Construímos o NFA
cada variável
Vi
V1
M tal que:
corresponde a um estado:
V3
V0
VF
V2
V4
estado final
especial 57
Para cada produção:
Vi  a1a2 amV j
adicionamos transições e os estados
intermediários requeridos
Vi
a1
a2
………
am V
j
58
Para cada produção:
Vi  a1a2 am
adicionamos transições e os estados
intermediários requeridos
Vi
a1
a2
………
am
VF
59
O NFA
M resultante tem a forma:
a9
a1
V0
a2
V1
a3
V3
a5
a4
a3
V2
Temos que:
a4
a5
a8
V4
a9
VF
L(G)  L( M )
60
O caso de Gramática Linear à Esquerda
Seja
G uma gramática linear à esquerda
Vamos provar:
L(G ) é regular
Idéia da Prova :
Construir uma gramática linear à
R
direita G com L(G )  L(G)
61
Como G é uma gramática linear à esquerda
as produções são da forma:
A  Ba1a2 ak
A  a1a2 ak
62
Construindo a gramática linear à direita
Em
G :
G
A  Ba1a2 ak
A ® Bv
Em
G
:
A  ak a2a1B
Av B
R
63
Construindo a gramática linear à direita
em
G :
G
A  a1a2 ak
Av
Em
G
:
A  ak a2a1
Av
R
64
L(G )  L(G)
É fácil ver que:
Como
R
G é linear à direita, temos:
L(G)
L(G)
Linguagem
Regular
Linguagem
Regular
R
L(G )
Linguagem
Regular
65
Prova - Parte 2
Linguagens
Geradas por
Gramáticas Regulares

Linguagens
Regulares
Toda linguagem regular L é gerada
por uma gramática regular G
66
Toda linguagem regular L é gerada
por uma gramática regular G
Idéia da Prova :
Seja
M um NFA com L  L(M ).
Construa, a apartir de M uma gramática
regular G tal que L( M )  L(G )
67
Como L é regular
existe um NFA M tal que
L  L(M )
b
Exemplo:
M
q0
a
q1
a

L  ab * ab(b * ab) *
L  L(M )
q2
b
q3
68
Convertendo M em uma gramática
b
linear à direita
M
q0
q0  aq1
a
q1
a

q2
b
q3
69
b
M
q0
q0  aq1
q1  bq1
q1  aq2
a
q1
a

q2
b
q3
70
b
M
q0  aq1
q1  bq1
q1  aq2
q0
a
q1
a

q2
b
q3
q2  bq3
71
L(G )  L( M )  L
b
G
q0  aq1
q1  bq1
q1  aq2
q2  bq3
M
q0
a
q1
a

q2
b
q3
q3  q1
q3  
72
Em Geral
a
Para cada transição:
q
Adicione a produção:
q  ap
variável
terminal
p
variável
73
Para cada estado final:
qf
Adicione a produção:
qf 
74
Como
G é uma gramática linear à direta
G é também uma gramática regular
com
L(G )  L( M )  L
75