Encontre uma gramática de estrutura de frase que gere cada uma destas linguagens.
c) o conjunto das seqüências de bits da forma w^{2}, em que w é uma seqüência de bits

Passo 1

O enunciado pede uma gramática de estrutura de frase (tipo-0) que gere
L=\{\,ww\mid w\in\{0,1\}^*\},
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},
\Sigma= {0,1},
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:
  1. S \to 0 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)
  2. T  0\to 0 T
    (o marcador T “passa por” um 0, deixando-o na mesma posição)
  3. T  1\to 1 T
    (o marcador T “passa por” um 1, deixando-o na mesma posição)
  4. T \to\epsilon
    (quando T chega no fim da cadeia, é removido)

Passo 4

Vamos explicar a dinâmica:
– Regra S \to 0 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  0\to 0 T e T  1\to 1 T) até o final e então T \to\epsilon 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.

Passo 5

Verificação por exemplo: gerar “0101” (=“01”²)
  1. S
  2. \to 0 S  03. \to 0 (1 S 1)  0= “01 S 10”
  3. \to 01 T  10 (usar S→T)
  4. \to 010 T  10 (usar T  0\to 0 T)
  5. \to 0101 T 0 (usar T  1\to 1 T)
  6. \to 01010 T (usar T  0\to 0 T)
  7. \to 01010 (ε) (usar T \to\epsilon)
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 \{ww\} é
V = {S,T},
\Sigma= {0,1},
P composta por
\begin{aligned} &S \to 0\,S\,0 \mid 1\,S\,1 \mid T,\\\ &T\,0\to 0\,T,\quad T\,1\to 1\,T,\quad T\to \varepsilon. \end{aligned}

Exercícios de Livros Relacionados