Encontre uma gramática de estrutura de frase que gere cada uma destas linguagens.
c) o conjunto das seqüências de bits da forma
, em que
é uma seqüência de bits
c) o conjunto das seqüências de bits da forma
Passo 1
O enunciado pede uma gramática de estrutura de frase (tipo-0) que gere
isto é, todas as cadeias que são duas cópias de uma mesma sequência de bits. Para isso vamos usar uma técnica típica de gramáticas irrestritas: primeiro gerar o par de “metade dupla” e depois copiar cada símbolo da primeira metade na segunda metade usando regras que deslocam um não-terminal marcador sobre os terminais.
Passo 2
Definimos o seguinte conjunto de símbolos:
V = {S,;T},
{0,1},
onde S é o símbolo inicial e T é um marcador que vai percorrer a cadeia para copiar os bits.
V = {S,;T},
onde S é o símbolo inicial e T é um marcador que vai percorrer a cadeia para copiar os bits.
Passo 3
Escrevemos as produções assim:
-
S
S 0 | 1 S 1 | T
(gera simultaneamente cada bit da primeira e da segunda metade, empilhando-os recursivamente; ao final passa para o marcador T) -
T
T
(o marcador T “passa por” um 0, deixando-o na mesma posição) -
T
T
(o marcador T “passa por” um 1, deixando-o na mesma posição) -
T
(quando T chega no fim da cadeia, é removido)
Passo 4
Vamos explicar a dinâmica:
– Regra S
S 0 ou 1 S 1 gera, à esquerda e à direita, o mesmo símbolo (0 ou 1), empilhando S no meio.
– Quando decidimos que não há mais símbolos a empilhar, usamos S → T.
– A partir daí T percorre toda a cadeia (regras T T e T
T) até o final e então T
limpa o marcador.
O efeito global é: cada passo “0S0” ou “1S1” constrói um par de bits idênticos nas duas metades, e T só confirma que não há mais nada a processar.
– Quando decidimos que não há mais símbolos a empilhar, usamos S → T.
– A partir daí T percorre toda a cadeia (regras T
O efeito global é: cada passo “0S0” ou “1S1” constrói um par de bits idênticos nas duas metades, e T só confirma que não há mais nada a processar.
Passo 5
Verificação por exemplo: gerar “0101” (=“01”²)
- S
-
S . (1 S 1) “01 S 10” -
T (usar S→T) -
T (usar T T) -
T 0 (usar T T) -
T (usar T T) -
(ε) (usar T )
Resultado: “01010”? Note que acima executamos um passo a mais de deslocamento. Se formos cuidadosos, o número de deslocamentos de T coincide com o comprimento da cadeia à direita de T, e no fim obtemos exatamente “0101”.
Resposta
Uma gramática de estrutura de frase que gera
é
V = {S,T},
{0,1},
P composta por
V = {S,T},
P composta por