Exercício 2. Mostre que toda linguagem regular é uma linguagem livre de contexto.
Dica: Construa uma GLC por indução sobre o número de operadores na expressão regular.

Passo 1

O enunciado pede para mostrar que toda linguagem regular é livre de contexto. Vamos usar indução estrutural sobre a expressão regular que define a linguagem. O conteúdo envolvido é: (a) definição de expressão regular e (b) construção de gramática livre de contexto (GLC) que gera exatamente a linguagem da expressão, usando regras de construção para os casos básicos e para os operadores \cup, concatenação e estrela de Kleene.

Passo 2

Base da indução: expressões sem operadores.
  1. Se a expressão regular é \emptyset, definimos a GLC G com símbolo inicial S e nenhuma produção que derive algo não vazio. Por exemplo,
S \;\to\;
(Nenhuma produção), de modo que L(G)=\emptyset.
2. Se a expressão regular é \varepsilon, usamos
S \;\to\; \varepsilon,
então L(G)=\{\varepsilon\}.
3. Se a expressão regular é um símbolo a\in\Sigma, usamos
S \;\to\; a,
então L(G)=\{a\}.

Passo 3

Passo da união: suponha que as expressões R_1 e R_2 já têm GLCs G_1=(V_1,\Sigma,P_1,S_1) e G_2=(V_2,\Sigma,P_2,S_2) tais que L(G_i)=L(R_i). Para R=R_1\cup R_2 construímos
G = (V_1\cup V_2\cup\{S\},\;\Sigma,\;P_1\cup P_2\cup\{S\to S_1\mid S_2\},\;S).
Então S pode derivar qualquer string de R_1 via S_1 ou de R_2 via S_2, garantindo L(G)=L(R_1)\cup L(R_2).

Passo 4

Passo da concatenação: com as mesmas G_1 e G_2 do passo anterior, para R=R_1R_2 definimos
G = (V_1\cup V_2\cup\{S\},\;\Sigma,\;P_1\cup P_2\cup\{S\to S_1\,S_2\},\;S).
A produção S\to S_1\,S_2 concatena qualquer derivação de R_1 seguida de qualquer derivação de R_2, de modo que L(G)=L(R_1)\,L(R_2).

Passo 5

Passo da estrela de Kleene: suponha G_1=(V_1,\Sigma,P_1,S_1) para R_1. Para R=R_1^* construímos
G = (V_1\cup\{S\},\;\Sigma,\;P_1\cup\{S\to S\,S_1\mid \varepsilon\},\;S).
Aqui S\to SS_1 gera repetições de fragmentos de L(R_1) e S\to\varepsilon garante que a estrela possa gerar a palavra vazia, concluindo L(G)=L(R_1)^*.

Passo 6

Pela construção acima, para qualquer expressão regular R podemos, por indução sobre o número de operadores em R, produzir uma GLC G tal que L(G)=L(R). Logo, toda linguagem regular é livre de contexto.

Resposta

Demonstrei, por indução estrutural sobre a expressão regular e pelas regras de construção de gramáticos livres de contexto, que cada operador preserva a natureza livre de contexto. Portanto, toda linguagem regular é livre de contexto.

Exercícios relacionados