Gramática livre de contexto para adição unária

StackOverflow https://stackoverflow.com/questions/1569958

Pergunta

Dado um alfabeto de 1s, quero analisar a adição do formulário

1^k + 1^j = 1^k+j

Isso é muito fácil de representar com um autômato pushdown simplesmente empurrando um 1 para a pilha em cada um dos dois primeiros 1s e depois aparecendo no último conjunto de 1s. No entanto, não consigo descobrir como representar isso como uma gramática livre de contexto, o que é obviamente possível desde o PDA == CFG.

Foi útil?

Solução

Meu conselho é criar um ponto de partida simples: 1+1 = 11 e agora tente descobrir como você pode "crescer" isso com expressões legais de CFG.

Como alternativa, resolvi isso agora, tentando estendê -lo com "parênteses correspondentes", que é um problema de introdução comum aos CFGs. É obviamente mais difícil, mas você pode encontrar um caminho frutífero dessa maneira.

Espero que isto ajude! Caçada feliz.

AGOR

Outras dicas

S => 1A1
A => 1A1 | +1B1
B => 1B1 | =

As duas primeiras linhas constroem o primeiro termo e a soma com o mesmo número de. Depois que o primeiro termo é construído, você passa para o segundo com "A => +1b1". A terceira linha constrói o segundo termo, adicionando simultaneamente um número igual de uma à soma. Depois de terminar, a transição igual termina.

Observe que isso não permite que nenhum termo na expressão seja igual a zero. Além disso, você pode construir expressões unárias menos com uma ligeira variação, tendo em mente que a - b = c é equivalente a a = b + c

Se você reescrever o RHS como 1^j1^k, então você deve ver que são apenas dois conjuntos aninhados de equilíbrio 1s. Combinado com um "caso base" de 1 + 1 = 11, você deve poder cultivar o "J" S por dentro e o "K" S do lado de fora.

Adição unária genérica não é possível com uma gramática livre de contexto ou com um autômato pushdown. Para esse tipo de computação, você deve usar uma máquina de Turing. Escrever um autômato pushdown que empurra 1's para a pilha não é válido porque a pilha não é realmente a saída de um PDA. A única saída de um PDA é um binário "aceitar" ou "rejeitar" que indica se a sequência de entrada é ou não uma parte do idioma reconhecido pelo PDA.

Sim, este está me incomodando na última hora.

Além disso, Cdiggins, 1 + 1 = 111 passaria que

Eu também tenho trabalhado sobre isso para sempre e não consigo fazer funcionar. É isso que faz mais sentido para mim:

A -> b + b = bb b -> bb b -> 1

Mas sim, isso aceita cordas como 1 + 111 = 11 e 11 + 1 = 111111 e outras bobagens. Parece que as pessoas aqui sabem, mas não têm vontade de compartilhar. Isso não é exatamente algo que podemos pesquisar no Google e obter ajuda significativa. Acha que você pode ser um pouco mais útil?

S   ->  1 + 1 = 11
S   ->  1S1
S   ->  1 + 1A11
A   ->  1 = 1
A   ->  1A1

Eu sei que é uma pergunta antiga, eu estava lendo Godel, Escher, Bach e foi atingido por um problema semelhante (de gerar uma gramática para o seu sistema PQ)

Então, para a pergunta do OP, acho que as seguintes regras de produção devem fazer:

Primeiro -> 1+segundo1 | 1First1 Second -> 1 = 1 | 1SEGOND1

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top