Erro no exemplo da Wikipedia CSG?

8

Estou confuso sobre o exemplo dado no artigo da Wikipedia sobre gramática sensível ao contexto:

https://en.wikipedia.org/wiki/Context-sensitive_grammar

Disclamer : Eu já mudei a seção discutida no artigo da wikipedia, portanto, o estado atual do artigo será diferente do que estou discutindo nesta pergunta. A versão original está aqui: https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&oldid=747616366

A seguinte gramática, com o símbolo inicial S, gera o idioma canônico não isento de contexto {anbncn: n ≥ 1}:

  1. S → abc
  2. S → a SB c
  3. c B → WB
  4. WB → WX
  5. WX → BX
  6. BX → B c
  7. b B → bb

Eles não afirmam diretamente que essa gramática é sensível ao contexto , mas a próxima frase implica que eles a consideram sensível ao contexto :

As regras 3 a 6 permitem trocar sucessivamente cada cB por Bc (quatro regras são necessárias para isso, uma vez que uma regra cB → Bc não se encaixaria no esquema αAβ → αγβ)

Então eles apelam para a forma canônica de regras gramaticais sensíveis ao contexto: αAβ → αγβ, implicando que toda a gramática é sensível ao contexto.

O que me deixa confuso é a regra nº 3 , que parece não se encaixar no esquema αAβ → αγβ. Considero o terminal aqui como parte de , variável como no esquema, está vazio. Isso implica que não pode produzir , pois deve ser salvo no mesmo local ( ).c B c cB A β c B W B cαBAβcBWBccBc

Perdi alguma coisa ou essa gramática foi realmente colocada aqui por engano (como não é realmente sensível ao contexto)?

Andrey Lebedev
fonte
1
Eu acho que você está certo.
Emil Jerabek
@ Looks EmilJeřábek como fizemos mudar nessa seção do artigo wiki ao mesmo tempo: Eu introduzido versão não adequado da gramática
Andrey Lebedev
Infelizmente, sua gramática está errada. Veja en.wikipedia.org/wiki/… .
Emil Jeřábek 3/11
@ EmilJeřábek Sinto muito, o que há de errado com a minha gramática (gramática de 9 regras) que eu coloquei na nova versão do artigo? Você poderia apontar qual regra está errada?
Andrey Lebedev
@ EmilJeřábek Ah, você quer dizer que essa gramática também pode produzir "aaa bb cccc"?
Andrey Lebedev

Respostas:

9

Se não me engano, é possível uma gramática CS mais simples. Aqui está:

  1. SABSc
  2. SAbc
  3. BAXA
  4. XAXY
  5. XYAY
  6. AYAB
  7. Aa
  8. Bbbb .

Uma derivação para a sequência éaaabbbccc

1ABSc1ABABScc2ABABAbccc3AXABAbccc4AXYBAbccc5AAYBAbccc6AABBAbccc36AABABbccc36AAABBbccc7...aaaBBbccc8aaaBbbccc8aaabbbccc

Jeffrey Shallit
fonte
3

Na verdade, como vários espectadores concordaram que a gramática original estava incorreta. Como @ EmilJeřábek notou, já havia discussões sobre esse problema aqui: https://en.wikipedia.org/wiki/Talk:Context-sensitive_grammar#Wrong_grammar_for_language

Portanto, parece que nem a gramática de 7 regras (que eu estava perguntando acima na minha pergunta), nem a gramática de 9 regras, que estava aqui antes e presente em artigos de outros idiomas, estão incorretas. Esta gramática de 9 regras:

  1. S → a BC
  2. S → a SBC
  3. CB → WB
  4. WB → WC
  5. WC → BC
  6. a B → ab
  7. b B → bb
  8. b C → bc
  9. c C → cc

é um exemplo incorreto, pois pode produzir palavras do formato " aaa bb cccc" `que não se encaixam na fórmula .anbncn

Por isso, sugiro o aprimoramento desta gramática, substituindo as regras 3-5 a quatro:

  1. S → a BC
  2. S → a SBC
  3. CB → CZ
  4. CZ → WZ
  5. WZ → WC
  6. WC → BC
  7. a B → ab
  8. b B → bb
  9. b C → bc
  10. c C → cc

As regras 3-6 ajudarão a evitar problemas com a substituição de CB para WB e depois de WC para BC.

EDIT : Como @ EmilJeřábek sugeriu novamente, as regras 7 e 8 podem ser simplificadas para uma regraBb.

Andrey Lebedev
fonte