Gramáticas regulares
Definição de gramática
Qualquer que seja a linguagem que se queira reconhecer, podemos sempre defini-las por intermédio de gramáticas.
Uma gramática é um quádruplo G = (T;N;S;P) onde:
T é um conjunto finito não vazio designado por alfabeto terminal, onde cada elemento é designado por símbolo terminal;
N é um conjunto finito não vazio, disjunto de T (N ∧ T = ∅), cujos elementos são designados por símbolos não terminais;
S ∈ N é um símbolo não terminal específico designado por símbolo inicial;
P é um conjunto finito de regras (ou produções) da forma a -> b onde a ∈ (T ∪ N)* N (T ∪ N)* e b ∈ (T ∪ N)*, isto é, a é uma cadeia de símbolos terminais e não terminais contendo, pelo menos, um símbolo não terminal; e b é uma cadeia de símbolos terminais e não terminais.
Definição de gramática regular
Uma gramática diz-se regular (à direita) se para qualquer produção (a -> b ∈ P) as duas condições seguintes são satisfeitas:
a ∈ N;
b ∈ T* ∪ T*N.
Alternativamente, podemos ter os não terminais (sempre) à esquerda:
a ∈ N;
b ∈ T* ∪ NT*
Para linguagem: {1}·T* ·{0} (T ={0;1}), temos uma gramática regular à direita: G = (T;{S;X;Y};S;P).
S -> 1X
X -> Y | 1X | 0X
Y -> 0
E no caso de uma gramática regular à esquerda:
S -> X0
X -> Y | X1 | X0
Y -> 1
Uma gramática regular gera uma linguagem regular.
As gramáticas regulares são também fechadas nas suas operações.
Isto é, aplicar uma qualquer das operações definidas sobre gramáticas regulares resulta também numa gramática regular.
Operações sobre gramáticas regulares
Operações sobre gramáticas regulares: reunião
Sejam G1 = (T1;N1;S1;P1) e G2 = (T2;N2;S2;P2) duas gramáticas regulares quaisquer com N1 · N2 = ∅.
A gramática G = (T;N;S;P) onde:
T = T1 ∪ T2
N = N1 ∪ N2 U {S}
S = S
P = { S -> S1, S -> S2} U P1 ∪ P2
é regular e gera a linguagem L = L(G1) ∪ L(G2).
A nova produção S -> Si, com i = 1; 2, permite que G gere a linguagem L(Gi)
Operações sobre gramáticas regulares: reunião (exemplo)
Sobre o conjunto de terminais T = {a;b;c}, determine uma gramática regular que represente a linguagem
L = L1 ∪ L2
sabendo que:
L1 = { aw : w ∈ T* }
L2 = { wa : w ∈ T* }
Vamos primeiro obter as GR que representam L1 e L2:
S1 -> aX1
X1 -> aX1 | bX1 | cX1 | ε
S2 -> aS2 | bS2 | cS2 | a
Teremos assim como resultado a gramática:
S -> S1 | S2
S1 -> aX1
X1 -> aX1 | bX1 | cX1 | ε
S2 -> aS2 | bS2 | cS2 | a
Operações sobre gramáticas regulares: concatenação
Sejam G1 = (T1;N1;S1;P1) e G2 = (T2;N2;S2;P2) duas gramáticas regulares quaisquer com N1 . N2 = ∅
A gramática G = (T;N;S;P) onde:
T = T1 ∪ T2
N = N1 ∪ N2
S = S1
P = { A -> wS2 : (A -> w) ∈ P1 ∧ w ∈ T1*} ∪ { A -> w : (A -> w) ∈ P1 ∧ w ∈ T1*N1} ∪ P2
é regular e gera a linguagem L = L(G1) · L(G2)
As produções da segunda gramática mantêm-se inalteradas.
As produções da primeira gramática que terminam num não terminal, também se mantêm inalteradas.
As produções da primeira gramática que só têm terminais ganham o símbolo inicial da segunda gramática no fim.
Operações sobre gramáticas regulares: concatenação (exemplo)
Sobre o conjunto de terminais T = {a;b;c}, determine uma gramática regular que represente a linguagem
L = L1 · L2
sabendo que:
L1 = { aw : w ∈ T* }
L2 = { wa : w ∈ T* }
Recuperando as GR que representam L1 e L2:
S1 -> aX1
X1 -> aX1 | bX1 | cX1 | ε
S2 -> aS2 | bS2 | cS2 | a
Teremos assim como resultado a gramática:
S -> S1 | S2
S1 -> aX1
X1 -> aX1 | bX1 | cX1 | ε
S2 -> aS2 | bS2 | cS2 | a
Operações sobre gramáticas regulares: fecho de Kleene
Seja G1 = (T1;N1;S1;P1) uma gramática regular qualquer.
A gramática G = (T;N;S;P) onde:
T = T1
N = N1 ∪ {S} com S ∉ N1
S = S1 | ε
P = { S -> S1 | ε } ∪ { A -> wS : (A -> w) ∈ P1 ∧ w ∈ T1*} ∪ { A -> w (A -> w) ∈ P1 ∧ w ∈ T1*N1}
é regular e gera a linguagem L = (L(G1))*
As produções que terminam num não terminal mantêm-se inalteradas
As produções só têm terminais ganham o símbolo inicial no fim
As novas produções (S -> S1 | e) garantem que (L(G1))n ⊃ L(G), para qualquer n ≥ 0.
Operações sobre gramáticas regulares: fecho de Kleene (exemplo)
Sobre o conjunto de terminais T = {a;b;c}, determine uma gramática regular que represente a linguagem
L = L1*
sabendo que
L1 = { aw : w ∈ T* }
Recuperando a GR que representa L1:
S1 -> aX1
X1 -> aX1 | bX1 | cX1 | ε
Teremos assim como resultado a gramática:
S -> S1 | ε
S1 -> aX1
X1 -> aX1 | bX1 | cX1 | S
Teorema da repetição para linguagens regulares
Das várias definições equivalentes para linguagens e gramáticas regulares, talvez a mais fácil de compreender seja a de que uma linguagem será regular sse existir um autómato finito que a reconheça.
Com esta definição é podemos com mais facilidade compreender que uma linguagem finita não só é sempre regular, como também o respectivo autómato não pode ter ciclos.
Em sentido inverso, podemos também concluir que uma linguagem regular infinita tem de ter pelo menos um ciclo.
Desta constatação podemos inferir que nas linguagens regulares infinitas, tem de ser sempre possível injectar (repetir) uma determinada sub-palavra as vezes que se quiser, mantendo a palavra resultante dentro da linguagem.
Visualmente, considerando um autómato finito para este tipo de linguagens, essa palavra será a que resulta do ciclo que necessariamente tem de existir (em linguagens infinitas).
Uma vez que o ciclo pode requerer palavras com uma dimensão mínima (suficiente para fechar o ciclo), esta condição (necessária mas não suficiente) requer um tamanho mínimo para palavras da linguagem.
Por outro lado, nos autómatos finitos (para linguagens infinitas) podemos sempre identificar um primeiro ciclo, i.e. um ciclo que aparece a uma distância finita do inicio da palavra.
Teorema da repetição (pumping lemma) para linguagens regulares:
Numa linguagem regular infinita L, existe um tamanho p tal que para todas as palavras w ∈ L para as quais: |w| ≥ p, podemos particionar w em três palavras: w = xyz, tal que:
|y| > 0 (padrão de repetição não vazio);
|xy| ≤ p (primeiro ciclo a uma distância finita do início da palavra);
∀k ≥ 0 · x · y^k · z ∈ L (pumping)
Note que esta é uma condição necessária para uma linguagem regular infinita, mas não suficiente.
Isto é, podem existir linguagens não regulares onde esta condição se verifique.
No entanto, a inexistência desta condição numa linguagem infinita é suficiente para determinar a sua não-regularidade.
Temos assim que este teorema pode ser aplicado para demostrar a não regularidade de linguagens.
Isto é, assumimos a regularidade da linguagem e vamos tentar demonstrar o oposto por contradição.
Para demostrar a regularidade de uma linguagem podemos aplicar as condições que definem linguagens e gramáticas regulares.
Exemplo 1
Determine a regularidade da linguagem L1 = {a^i · b^i : i ≥ 0}.
Em primeiro lugar note que não é possível aplicar a condição da concatenação, porque há uma dependência no número de repetições dos símbolos a e b. Isto é, muito embora quer a^i, quer b^i, (i ≥ 0) sejam regulares, o número de repetições i tem de ser o mesmo (condição não garantida pela concatenação).
Dito de outra forma: a^i · b^i ≠ a* · b*
Uma vez que a linguagem é infinita então, para ser regular, o teorema da repetição tem ser aplicável.
Seja w = a^n · b^n. Então |w| = 2n.
Para particionar w = xyz temos três possibilidades: y contém só sequências de a’s, só sequências de b’s, ou uma sequência com prefixos de a’s e sufixos de b’s.
Os dois últimos casos quebram desde logo a condição |xy| ≤ p já que o x terá de conter a’s e existem tantas palavras em L1 quantas se queira com um número não limitado de a’s em x.
Resta o primeiro caso.
Seja x = a^p; y = a^q; z = a^r · b^n, então p+q+r = n para que w ∈ L1 e q ≠ 0.
Como xy^2 · z ∉ L1 (uma vez que q+2 * q+r ≠ n), então L1 não é regular.
Exemplo 2
Determine a regularidade da linguagem L2 = {c^k · a^i · b^i : k ≥ 0 ⊥ i ≥ 0}.
Repare que neste caso o teorema da repetição aplica-se (y = c). No entanto seria estranho que esta linguagem fosse regular uma vez que contém a linguagem anterior (que não era regular).
Não há aqui nenhuma contradição porque o teorema da repetido é uma condição necessária, mas não suficiente.
Para determinar a regularidade neste caso temos de aplicar as operações aplicáveis a linguagens regulares.
Assim: L2 = {c^k : k ≥ 0} · L1
A linguagem {c^k : k ≥ 0} é regular, mas L1 não o é, pelo que L2 também não vai ser.
Last updated
