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.
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
, concatenação e estrela de Kleene.
Passo 2
Base da indução: expressões sem operadores.
- Se a expressão regular é
, definimos a GLC com símbolo inicial e nenhuma produção que derive algo não vazio. Por exemplo,
(Nenhuma produção), de modo que
.
2. Se a expressão regular é , usamos
2. Se a expressão regular é
então
.
3. Se a expressão regular é um símbolo , usamos
3. Se a expressão regular é um símbolo
então
.
Passo 3
Passo da união: suponha que as expressões
e
já têm GLCs
e
tais que
. Para
construímos
Então
pode derivar qualquer string de
via
ou de
via
, garantindo
.
Passo 4
Passo da concatenação: com as mesmas
e
do passo anterior, para
definimos
A produção
concatena qualquer derivação de
seguida de qualquer derivação de
, de modo que
.
Passo 5
Passo da estrela de Kleene: suponha
para
. Para
construímos
Aqui
gera repetições de fragmentos de
e
garante que a estrela possa gerar a palavra vazia, concluindo
.
Passo 6
Pela construção acima, para qualquer expressão regular
podemos, por indução sobre o número de operadores em
, produzir uma GLC
tal que
. 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.