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}:
- S → abc
- S → a SB c
- c B → WB
- WB → WX
- WX → BX
- BX → B c
- 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 …B A β c B W B c
Perdi alguma coisa ou essa gramática foi realmente colocada aqui por engano (como não é realmente sensível ao contexto)?
fonte
Respostas:
Se não me engano, é possível uma gramática CS mais simples. Aqui está:
Uma derivação para a sequência éa a a b b b c c c
fonte
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:
é um exemplo incorreto, pois pode produzir palavras do formato "umanbncn
aaa bb cccc
" `que não se encaixam na fórmula .Por isso, sugiro o aprimoramento desta gramática, substituindo as regras 3-5 a quatro:
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 regraB → b .fonte