03 - Gramáticas Regulares

03 · Gramáticas Regulares e Hierarquia de Chomsky

Resumo em 30 segundos

Uma gramática $G=(V_n,V_t,S,P)$ é um mecanismo gerador: a partir do símbolo inicial $S$, aplicamos regras de reescrita até sobrar só terminais. O formato das regras classifica a gramática na Hierarquia de Chomsky (tipos 3, 2, 1, 0). As do tipo 3 (regulares, forma $A\to aB$ ou $A\to a$) geram exatamente as linguagens que os autômatos finitos reconhecem (aula 07).

Anterior: 02 - Matemática Discreta · Voltar ao mapa · Próxima: 03b - Expressões Regulares

---

Slide 3: tipos de linguagens

Tipo	Descrição	Exemplo
Finita	número finito de sentenças	comandos de um equipamento
”Vazia”	só a sentença vazia	$\{\epsilon \}$
Infinita	número infinito de sentenças (a maioria)	$\{0^n{1}^n\mid n>0\}$

"Linguagem vazia" tem dois sentidos

O slide chama de vazia a linguagem que tem apenas $\epsilon$, ou seja, $\{\epsilon \}$. Em muitos livros, “linguagem vazia” é $\varnothing$ (nenhuma palavra). São coisas diferentes: $\{\epsilon \}$ tem uma palavra; $\varnothing$ tem zero. Use a notação de conjunto para não ter ambiguidade.

Slide 4: formas de representar uma linguagem

1. Listar as palavras: só funciona se a linguagem for finita.
2. Descrição algébrica: por exemplo $\{a^n{b}^n{c}^n\}$, com $a^n=\underset{n}{\underbrace{aa\dots a}}$.
3. Algoritmo que reconhece: dada uma palavra, responde se pertence. Exemplo: autômato finito.
4. Mecanismo que gera: produz todas as palavras em alguma ordem. Exemplo: gramática.

Provável erro de digitação no slide 4

O exemplo aparece como $\{a^n{b}^n{c}^n\mid n<0\}$. Com $n<0$ o conjunto seria vazio, já que não existe repetição negativa. O esperado é $n>0$ ou $n\ge 0$.

Slides 5 a 7: definição de gramática

Gramática é um dispositivo formal para especificar uma linguagem potencialmente infinita de forma finita.

$G=(V_n,V_t,S,P)$

Componente	O que é	Convenção usual
$V_n$	não terminais (metassímbolos, “variáveis”)	letras maiúsculas
$V_t$	terminais (os símbolos que aparecem nas palavras)	minúsculas, dígitos
$S$	símbolo inicial, $S\in V_n$
$P$	produções (regras de reescrita) $\alpha \to \beta$

Restrições do slide 7:

• $V=V_n\cup V_t$ é o vocabulário, e $V_n\cap V_t=\varnothing$ (um símbolo não pode ser terminal e não terminal ao mesmo tempo).
• Cada produção $\alpha \to \beta$ tem $\alpha \in V^{+}$ contendo pelo menos um não terminal e $\beta \in V^{\ast }$.
• $\epsilon$ só pode aparecer do lado direito. A regra $\alpha \to \epsilon$ se chama regra nula ou regra épsilon.

Slide 8: exemplo, gramática de números inteiros

$V_n=\{I,D\}$, $V_t=\{0,\dots ,9\}$, $S=I$ e

$P=\{I\to D\mid DI,D\to 0\mid 1\mid \cdots \mid 9\}$

Derivação de 036: $I\Rightarrow DI\Rightarrow 0I\Rightarrow 0DI\Rightarrow 03I\Rightarrow 03D\Rightarrow 036$.

O problema apontado no slide: ela gera zeros à esquerda (00036).

Exercício do slide 8: gramática sem zeros à esquerda

Ideia: o primeiro dígito tem regra diferente dos demais. Ou é o número 0 sozinho, ou começa com 1 a 9.

$I\to 0\mid P\mid PRR\to D\mid DRP\to 1\mid \cdots \mid 9D\to 0\mid \cdots \mid 9$

Versão já no formato regular (útil para a aula 07):

$I\to 0\mid 1\mid \cdots \mid 9\mid 1R\mid \cdots \mid 9RR\to 0\mid \cdots \mid 9\mid 0R\mid \cdots \mid 9R$

Conferi por programa que a versão regular gera exatamente $\{0\}\cup \{$números de 1 a 3 dígitos sem zero à esquerda$\}$ quando limitada a 3 dígitos.

Derivações

Slides 9 e 10.

• Produção $\alpha \to \beta$: a regra. Derivação $\alpha \Rightarrow \beta$: a aplicação de uma regra.
• Formalmente: $\gamma A\delta \Rightarrow \gamma \beta \delta$ se $A\to \beta \in P$ (substitui uma ocorrência de $A$, o contexto $\gamma ,\delta$ fica igual).
• ${\Rightarrow }^{\ast }$: zero ou mais passos. ${\Rightarrow }^{+}$: um ou mais. ${\Rightarrow }^n$: exatamente $n$. É o mesmo $R^{\ast }$ / $R^{+}$ de Matemática Discreta.

Conceito	Definição	Símbolos
Sentença	só terminais, derivada de $S$	$S{\Rightarrow }^{+}w$, $w\in V_t^{\ast }$
Forma sentencial	mistura de terminais e não terminais, derivada de $S$	$S{\Rightarrow }^{\ast }\beta$, $\beta \in V^{\ast }$
Linguagem gerada	todas as sentenças	$L(G)=\{w\in V_t^{\ast }\mid S{\Rightarrow }^{\ast }w\}$

(O slide 10 escreve "$w{V}_t^{\ast }$"; falta o $\in$.)

Slide 11: exemplo 0ⁿ1ⁿ

$G=(\{S\},\{0,1\},S,\{S\to 01\mid 0S1\})$

$S\Rightarrow 0S1\Rightarrow 00S11\Rightarrow 0^{3}S{1}^3\Rightarrow \cdots \Rightarrow 0^{n-1}S{1}^{n-1}\Rightarrow 0^n{1}^n$

$L(G)=\{0^n{1}^n\mid n>0\}$.

Complemento: essa linguagem NÃO é regular

Repare que $S\to 0S1$ tem terminais dos dois lados do não terminal. Isso não é do tipo 3. E não é só essa gramática: nenhuma gramática regular gera $0^n{1}^n$, porque um autômato finito teria que “lembrar” quantos zeros leu, e ele só tem memória finita. A prova formal usa o Lema do Bombeamento, que os livros trazem (no livro de Ramos: seção 3.9 “Linguagens que não são Regulares”, p. 233).

Slide 12: exercício de derivações

$G$: $S\to ASBB\mid BSAA\mid 0$, $A\to 01\mid 01A$, $B\to 10\mid 10B$.

Derivação de 0101010

Tamanho 7. Com $S\to ASBB$, o menor possível é $A=01$, $S=0$, $B=10$, $B=10$: 01+0+10+10 = 0101010.

$S\Rightarrow ASBB\Rightarrow 01SBB\Rightarrow 010BB\Rightarrow 01010B\Rightarrow 0101010$

Derivação de 101000101010101

Começa com 10, então use $S\to BSAA$ (começa com $B$, que gera 10...).

$\begin{array}{rl}S& \Rightarrow BSAA\Rightarrow 10BSAA\Rightarrow 1010SAA\Rightarrow 10100AA\\ & \Rightarrow 1010001A\Rightarrow 101000101A\Rightarrow 10100010101A\\ & \Rightarrow 1010001010101A\Rightarrow 101000101010101\end{array}$

Leitura em blocos: $B=\text{1010}$ (usou $B\to 10B$ e $B\to 10$), $S=\text{0}$, primeiro $A=\text{01}$, segundo $A=\text{01010101}$. As duas derivações foram encontradas e conferidas por busca automática.

Slide 13: Hierarquia de Chomsky

Tipo	Nome	Forma das produções	Linguagens	Reconhecedor (complemento)
3	Regular	$A\to aB$ ou $A\to a$	Regulares (LR)	Autômato finito
2	Livre de contexto	$A\to \beta$, com $A\in V_n$, $\beta \ne \epsilon$	Livres de contexto (LLC)	Autômato com pilha
1	Sensível ao contexto	$\alpha \to \beta$ com $|\alpha |\le |\beta |$	Sensíveis ao contexto (LSC)	Autômato linearmente limitado
0	Irrestrita	$\alpha \to \beta$, $\alpha \in V^{+}$, $\beta \in V^{\ast }$	Recursivamente enumeráveis (LRE)	Máquina de Turing

A coluna “reconhecedor” não está nos slides; é o resultado clássico da teoria e aparece nos dois livros de referência.

Como classificar uma gramática, na prática:

flowchart TD
  A{"Todo lado esquerdo é<br/>um único não terminal?"} -- não --> B{"tamanho de α ≤ tamanho de β<br/>em todas as regras?"}
  B -- sim --> T1[Tipo 1]
  B -- não --> T0[Tipo 0]
  A -- sim --> C{"Todo lado direito é<br/>aB ou a (ou tudo linear<br/>para o mesmo lado)?"}
  C -- sim --> T3[Tipo 3 · Regular]
  C -- não --> T2[Tipo 2 · Livre de contexto]

A gramática recebe o tipo mais restrito que ela satisfaz.

Slide 14: gramáticas lineares

Forma	Produções ($w\in V_t^{\ast }$)
Linear à direita	$A\to wB$ ou $A\to w$
Linear à esquerda	$A\to Bw$ ou $A\to w$
Linear unitária à direita	à direita com $|w|=1$
Linear unitária à esquerda	à esquerda com $|w|=1$

As quatro são equivalentes e toda gramática regular é linear (e vice-versa).

Não misture os lados

A equivalência vale quando todas as produções são lineares para o mesmo lado. Uma gramática com algumas regras $A\to aB$ e outras $A\to Ba$ pode gerar linguagens não regulares. Esse detalhe não está no slide, mas é uma pegadinha comum de prova.

Slide 15: hierarquia como conjuntos

Tipo 3 ⊂ Tipo 2 ⊂ Tipo 1 ⊂ Tipo 0.

flowchart TB
  subgraph T0["Tipo 0 · Irrestritas (LRE)"]
    subgraph T1["Tipo 1 · Sensíveis ao contexto"]
      subgraph T2["Tipo 2 · Livres de contexto"]
        subgraph T3["Tipo 3 · Regulares"]
          r["a*b*"]
        end
        cf["0ⁿ1ⁿ · ww^R"]
      end
      cs["aⁿbⁿcⁿ"]
    end
  end

Os exemplos dentro de cada nível são clássicos (a capa do livro de Ramos, José Neto e Vega, inclusive, desenha essa hierarquia com exemplos parecidos).

Slide 16: exercício de classificação

$G$: $S\to aB\mid Ba$, $A\to a\mid aS\mid bAA$, $B\to b\mid bS\mid aBB$.

Tipo da gramática

• Todo lado esquerdo é um único não terminal, então é pelo menos tipo 2.
• $B\to aBB$ tem dois não terminais no lado direito, e $S\to aB$ / $S\to Ba$ misturam linearidade à direita e à esquerda. Não é regular.
• Resposta: tipo 2 (livre de contexto).

Linguagem gerada (com um alerta)

Observações, conferidas enumerando todas as palavras geradas até tamanho 8:

1. O não terminal $A$ é inacessível: não aparece em nenhum lado direito alcançável a partir de $S$. As regras de $A$ nunca são usadas.
2. Toda palavra gerada tem o mesmo número de a e b.
3. Mas nem toda palavra com $\#a=\#b$ é gerada. Exemplos que faltam: baab, abbaab, baaabb.

Isso sugere um erro de digitação: a gramática clássica é $S\to aB\mid bA$ (com $A$ e $B$ iguais aos do slide). Com essa correção, conferi que ela gera exatamente $\{w\in \{a,b{\}}^{+}\mid \#a(w)=\#b(w)\}$.

Intuição da versão corrigida: $A$ gera palavras com um a a mais que b; $B$ gera palavras com um b a mais que a. $S\to aB$ junta um a com “um b a mais”, resultando em equilíbrio.

Confirme com o professor qual versão ele quis. Se for a do slide mesmo, a resposta honesta é: “um subconjunto próprio das palavras com igual número de a e b”.

Slide 17: linguagens de cada tipo

• LR: geradas por gramáticas tipo 3.
• LLC: tipo 2.
• LSC: tipo 1.
• LRE: tipo 0, associadas a Máquinas de Turing, computabilidade e funções parciais recursivas.

Slides 18 a 20: gramáticas com regra vazia

Pela definição, gramáticas regulares e livres de contexto não geram $\epsilon$. Para incluir $\epsilon$:

1. Se $S$ não aparece do lado direito de nenhuma produção: basta acrescentar $S\to \epsilon$. Resultado: $L(G^{\prime })=L(G)\cup \{\epsilon \}$.
2. Se $S$ aparece do lado direito: criar um novo inicial $S^{\prime }$, copiar para $S^{\prime }$ as produções de $S$ e acrescentar $S^{\prime }\to \epsilon$.

Por que a regra 2 existe

Se $S$ aparece à direita e você põe $S\to \epsilon$ direto, o $\epsilon$ pode ser usado no meio de uma derivação e gerar palavras novas, não só a vazia. Com $S^{\prime }$, o $\epsilon$ só pode ser usado no primeiro passo.

(O slide 19 diz “acrescentar a regra $S\to \epsilon$” no último passo; pelo exemplo do slide 20, a regra acrescentada é $S^{\prime }\to \epsilon$.)

Exemplos do slide 20:

	Gramática original	$L(G)$	Com $\epsilon$
1	$S\to aA$, $A\to aA\mid a$	$a^n$, $n\ge 2$	$S\to aA\mid \epsilon$ ($S$ não aparece à direita)
2	$S\to aA$, $A\to aS\mid a$	$a^{2k}$, $k\ge 1$	$S^{\prime }\to aA\mid \epsilon$, $S\to aA$, $A\to aS\mid a$

Slide 21: exercícios

L₁ = { aⁿbᵐ | n ≥ 0, m ≥ 1 }

$S\to aS\mid bB\mid bB\to bB\mid b$
Já é regular (tipo 3). Conferido por programa até tamanho 8.

L₂ = { aⁿbᵐcⁿ | n ≥ 0, m ≥ 1 }

$S\to aSc\mid BB\to bB\mid b$
Tipo 2. O número de a precisa bater com o de c, e isso exige a regra “embrulhando” $aSc$. Conferido até tamanho 9.

Gramática regular: w ∈ {0,1}* sem 1s consecutivos

$S$ = “o último símbolo não foi 1”; $A$ = “o último foi 1”.
$S\to 0S\mid 1A\mid \epsilon A\to 0S\mid \epsilon$
Inclui $\epsilon$ porque $w\in \{0,1{\}}^{\ast }$. Como $S$ aparece à direita, a versão estrita pela regra dos slides 18 a 20 seria: $S^{\prime }\to 0S\mid 1A\mid 0\mid 1\mid \epsilon$, $S\to 0S\mid 1A\mid 0\mid 1$, $A\to 0S\mid 0$. Conferido até tamanho 9.

GLC: w ∈ {0,1,2}* com todos os 0s consecutivos

Estrutura: (qualquer coisa sem 0) (bloco de zeros) (qualquer coisa sem 0).
$S\to XZXX\to 1X\mid 2X\mid \epsilon Z\to 0Z\mid \epsilon$
Conferido até tamanho 7. Essa linguagem é regular também (a ER é $(1|2{)}^{\ast }{0}^{\ast }(1|2{)}^{\ast }$), mas o exercício pede só uma GLC.

---

Aprofundamento com os livros

Páginas das edições da sua pasta: Menezes 3ª edição (2000) e Ramos, José Neto e Vega (Bookman).

Cada autor escreve a gramática de um jeito

Fonte	Quádrupla	Observação
Slides	$G=(V_n,V_t,S,P)$	$V_n$ não terminais, $V_t$ terminais
Menezes (Def. 1.27, p. 23)	$G=(V,T,P,S)$	$V$ = variáveis (não terminais), $T$ = terminais
Ramos (p. 91)	$G=(V,\Sigma ,P,S)$	$V$ = vocabulário inteiro (terminais e não terminais); os não terminais são $N=V-\Sigma$

O mesmo $V$ significa coisas diferentes

No Menezes, $V$ são só as variáveis. No Ramos, $V$ é tudo. O próprio Ramos avisa numa nota de rodapé (p. 91) que a ordem e os nomes mudam de autor para autor e que é preciso conferir a notação antes de ler. Na prova, use a notação do professor.

O Menezes define a linguagem gerada com ${\Rightarrow }^{+}$: $L(G)=\{w\in T^{\ast }\mid S{\Rightarrow }^{+}w\}$ (Def. 1.29, p. 24). O Ramos chama de derivação não trivial a que usa pelo menos uma produção (p. 92).

O exercício do slide 8 está no Menezes

O Exemplo 22 do Menezes (p. 24 e 25) é a mesma gramática de números naturais dos slides ($S\to D\mid DS$, $D\to 0\mid \cdots \mid 9$), e o livro também sugere como exercício fazer uma versão que não aceite zeros à esquerda. Ele ainda pergunta se existe mais de uma derivação para 243.

Existe mais de uma derivação para 243 nessa gramática?

Minha resposta: sim. A palavra é a mesma, mas a ordem das substituições pode mudar. Uma derivação troca sempre o não terminal mais à esquerda ($S\Rightarrow DS\Rightarrow 2S\Rightarrow 2DS\Rightarrow \dots$); outra pode primeiro expandir todos os $S$ e só depois os $D$ ($S\Rightarrow DS\Rightarrow DDS\Rightarrow DDD\Rightarrow 2DD\Rightarrow \dots$). Nas duas, a estrutura é a mesma; só a ordem dos passos muda.

Gramáticas lineares, com os exemplos do Menezes (seção 2.6, p. 55 a 57)

O Menezes define quatro formas (Def. 2.15, p. 55), com $w\in T^{\ast }$:

Forma	Produções
Linear à direita (GLD)	$A\to wB$ ou $A\to w$
Linear à esquerda (GLE)	$A\to Bw$ ou $A\to w$
Linear unitária à direita (GLUD)	como GLD, com $|w|\le 1$
Linear unitária à esquerda (GLUE)	como GLE, com $|w|\le 1$

Diferença sutil em relação ao slide 14

O slide pede $|w|=1$ nas formas unitárias. O Menezes pede $|w|\le 1$, o que permite também $A\to B$ e $A\to \epsilon$. E para o Menezes, gramática regular é qualquer gramática linear (Def. 2.17, p. 56).

A mesma linguagem $a(ba{)}^{\ast }$ nas quatro formas (Exemplo 14 do Menezes, p. 56). Conferi por programa que as quatro geram exatamente $a(ba{)}^{\ast }$ até tamanho 11:

Forma	Produções
GLD	$S\to aA$, $A\to baA\mid \epsilon$
GLE	$S\to Sba\mid a$
GLUD	$S\to aA$, $A\to bB\mid \epsilon$, $B\to aA$
GLUE	$S\to Aa\mid a$, $A\to Sb$

Repare como a GLE “constrói de trás para frente”: $S\Rightarrow Sba\Rightarrow Sbaba\Rightarrow ababa$.

Outro exemplo do livro (Exemplo 15, p. 56 e 57), para $(a+b{)}^{\ast }(aa+bb)$: GLD $S\to aS\mid bS\mid A$, $A\to aa\mid bb$; GLE $S\to Aaa\mid Abb$, $A\to Aa\mid Ab\mid \epsilon$. Também conferido.

Como o Ramos transforma uma forma em outra (seção 3.1, p. 141 a 145)

• Direita para esquerda (Algoritmo 3.1): obtenha uma GLD para o reverso da linguagem e inverta os lados direitos das regras. A linguagem é a mesma; só muda o sentido em que as palavras são construídas.
• Várias letras numa regra para uma letra por regra (Algoritmo 3.3): uma regra como $S\to abcdP$ vira uma cadeia de regras com não terminais novos: $S\to a{P}_1$, $P_1\to b{P}_2$, $P_2\to c{P}_3$, $P_3\to dP$ (Exemplo 3.2, p. 145). É isso que deixa a gramática pronta para virar autômato na aula 07.

A Hierarquia de Chomsky no Ramos (seção 2.6, p. 105 a 110)

Dois detalhes que mudam em relação aos slides:

1. Tipo 2 com $\epsilon$: o Ramos aceita produções livres de contexto com lado direito vazio ($\beta \in V^{\ast }$, p. 107). O slide 13 exige $\beta \ne \epsilon$. Por isso o Ramos observa que nem toda gramática tipo 2 é tipo 1: a regra $S\to \epsilon$ quebra a condição $|\alpha |\le |\beta |$ (p. 108).
2. Tipo 1 e $\epsilon$: como as regras nunca encolhem a forma sentencial, uma gramática sensível ao contexto não gera $\epsilon$. A convenção adotada é considerar $L$ sensível ao contexto se $L-\{\epsilon \}$ for (p. 107).

Por que existem exatamente essas quatro classes? O Ramos dá uma explicação estrutural (p. 109 e 110) que ajuda muito a decorar:

Classe	O que ela consegue expressar que a anterior não consegue	Exemplo em programação
Regular	sequências e repetições simples	números, identificadores
Livre de contexto	aninhamento	parênteses balanceados, blocos { }
Sensível ao contexto	dependência de contexto: algo num ponto da cadeia depende de algo em outro ponto	uma variável só pode ser usada se foi declarada
Recursivamente enumerável	tudo que uma Máquina de Turing faz; aqui aparece a indecidibilidade (não há algoritmo geral para dizer se uma cadeia pertence)

O Menezes cita o mesmo caso de declaração e uso de variáveis como algo que as livres de contexto não resolvem (cap. 5, p. 154 e 155).

Uma gramática sensível ao contexto de verdade (Ramos, Exemplo 2.24, p. 93 e 94)

Para $\{a^n{b}^n{c}^n\mid n\ge 1\}$:
$S\to aSBC\mid abCCB\to BCbB\to bbbC\to bccC\to cc$
A ideia: $S$ gera os $a$ e deixa uma fila de pares $BC$; a regra $CB\to BC$ “ordena” a fila, empurrando os $B$ para a esquerda; depois as regras com contexto ($bB$, $bC$, $cC$) trocam as variáveis por terminais da esquerda para a direita. Derivação de aabbcc: $S\Rightarrow aSBC\Rightarrow aabCBC\Rightarrow aabBCC\Rightarrow aabbCC\Rightarrow aabbcC\Rightarrow aabbcc$. Conferi por programa que ela gera abc, aabbcc, aaabbbccc e aaaabbbbcccc e nada mais até tamanho 12. Repare que $CB\to BC$ tem dois símbolos no lado esquerdo: por isso não é livre de contexto.

Essa gramática resolve o exercício 1.21 do Menezes. Se o exercício pedir $n\ge 0$, acrescente $\epsilon$ com um novo inicial $S^{\prime }\to S\mid \epsilon$, como no slide 19.

O Menezes também mostra (Exemplo 23, p. 25) uma gramática irrestrita para $\{ww\mid w\in \{a,b{\}}^{\ast }\}$. A técnica é bonita: cada terminal gerado na primeira metade deixa uma variável “mensageira” que caminha pela palavra até o marcador do meio e lá vira o terminal correspondente da segunda metade.

Exercícios extras do Menezes (p. 30)

1.19: gramática para identificadores de Pascal (letra seguida de letras ou dígitos). E com no máximo seis caracteres?

Minha resposta, com $L$ para letras e $D$ para dígitos:
$S\to LRR\to LR\mid DR\mid \epsilon L\to a\mid \cdots \mid zD\to 0\mid \cdots \mid 9$
Para no máximo seis caracteres, troque a recursão por uma contagem: $S\to L{R}_5$, $R_k\to L{R}_{k-1}\mid D{R}_{k-1}\mid \epsilon$ para $k=5,\dots ,1$, e $R_0\to \epsilon$. Cada $R_k$ permite no máximo mais $k$ símbolos.

1.20: gramática para expressões com parênteses, operadores + e * e operando x

Minha resposta:
$E\to E+T\mid TT\to T\ast F\mid FF\to (E)\mid x$
Conferi por programa que ela gera x*(x+x) e (((((x))))) e não gera x+. A versão mais curta $E\to E+E\mid E\ast E\mid (E)\mid x$ também gera a linguagem, mas é ambígua (a mesma expressão tem duas árvores). Separar em $E$, $T$, $F$ embute a precedência de * sobre +. Esse assunto (ambiguidade) é do capítulo de livres de contexto.

Para aprofundar nos livros

Onde ler (páginas das edições da sua pasta)

• Menezes (3ª ed.): 1.5, gramática e derivação, p. 23 a 26; 2.6 Gramática Regular, p. 55 a 60; cap. 5 (Hierarquia de Chomsky), p. 153 a 155; exercícios 1.19 a 1.21, p. 30.
• Ramos, José Neto e Vega: 2.3 Gramáticas, p. 90 a 94; 2.4 Linguagens, Gramáticas e Conjuntos, p. 94 a 96; 2.6 Hierarquia de Chomsky, p. 105 a 110; 3.1 Gramáticas Regulares, p. 141 a 145; 3.9 Linguagens que não são Regulares, p. 233 a 239.
• A prova de que $0^n{1}^n$ não é regular (Lema do Bombeamento) está resumida em 08 - Tópicos Complementares dos Livros.

Relacionadas: 03b - Expressões Regulares · 07 - Equivalência AF e GR · Glossário · Flashcards