Gramática livre de contexto para $ l= {u \ #v \ meados u, v \ in \ {a, b} ^ *, \ vert u vert_a \ neq \ tex v \ vert_a \ text {ou} \ vert u\ Vert_b \ neq \ vert v \ vert_b} $

Question

Eu tento encontrar uma gramática livre de contexto para a linguagem $ l= {u \ #v \ meados de u, v \ in \ {a, b} ^ *, \ Vert U \ Vert_A \ Neq \ Vert v \ Vert_A \ Texto {ou} \ Vert u \ vert_b \ neq \ vert v \ vert_b} $ . Há uma dica na tarefa que se deve primeiro construir a gramática livre de contexto para casos, como $ l_1= {u \ #v \ meados de u, v \ in \ {a, b} ^ *, \ vert u \ vert_a> \ vert v \ vert_a \} $ e posteriormente combine tudo isso.

Eu apreciaria uma dica para chegar a $ l_1 $ . Eu não sei como construir $ u \ #V $ tal que $ u $ e $ v $ são gratuitos independentes um do outro, exceto do fato de que $ u $ tem mais $ a $ 'do que $ v $ . Eu tentei construir minha linguagem em torno da $ \ # $ e também tentei mover a $ \ # $ Na direção da maioria aparente $ a $ , mas nenhuma das minhas tentativas funcionou.

Qual é a maneira correta de abordar essas construções em geral?

Answer 1

Vou apenas mostrar como construir uma gramática para $ l_1= {u \ #v, | u | _a> | v | _a \} $ .Então vai ser direto combinar 4 gramáticas semelhantes em uma gramática para $ l $ .

A ideia é escrever $ u \ #V $ como $ Xay \ #V $ com $ x, y, v \ in \ {a, b \} ^ * $ e $ | y | _a= |v | _a $ .A construção de $ y \ #V $ é tratado pela não-terminal $ z $ que "cresce"É do centro.

$$ \ começo {alinhar *} S & \ como como \ Mid Bs \ Mid AZ \\ Z & \ to bz \ mid zb \ mid aza |\, \ # \ final {alinhar *} $$