S -> bA|aB
A -> a|aS|bAA
B -> b|bS|aBB
Qualsiasi metodo semplice diverso dal tentativo di trovare una stringa che generi due alberi di analisi?come posso dimostrare che questa grammatica è ambigua?
Qualcuno può darmi una stringa che può provarlo.
Non esiste un metodo semplice per dimostrare una grammatica context-free ambigua - infatti, the question is undecidable, mediante riduzione allo Post correspondence problem.
sì, ma non posso scriverlo sul foglio delle risposte . Quali attributi della grammatica dovrei guardare per selezionare correttamente la stringa che dà origine a 2 alberi di analisi? – crowso
@user: secondo la mia copia di Hopcroft e Ullman, dovresti considerare la stringa "aaabbabbba" e trovare una derivazione di sinistra, una derivazione di destra e un albero di analisi usando la grammatica che hai specificato. Speriamo che, con la soluzione per l'esercizio 4.8 in mano, il resto diverrà chiaro! –
c'è un modo per creare una stringa? – crowso
C'è una stringa però: bbaaba
S -> bA -> bbAA -> bbaA -> bbaaS -> bbaabA -> bbaaba
S -> bA -> bbAA -> bbaSA -> bbaaBA -> bbaabA -> bbaaba
@crowso dovresti scegliere questa come risposta corretta – Yugi
per me questo sembra il suo inequivocabile. – crowso
Consentitemi di darvi il benvenuto su StackOverflow e di ricordare tre cose che facciamo di solito qui: 1) Come ricevete aiuto, provate a darlo anche ** rispondendo alle domande ** nella vostra area di competenza 2) ['Leggi le FAQs] (http://tinyurl.com/2vycnvr) 3) Quando vedi una buona sessione di domande e risposte, votali [usando i triangoli grigi] (http://i.imgur.com/kygEP.png), come la credibilità del il sistema si basa sulla reputazione che gli utenti ottengono condividendo le proprie conoscenze. Ricorda inoltre di accettare la risposta che risolve meglio il tuo problema, se ce n'è uno, ['premendo il segno di spunta'] (http://i.imgur.com/uqJeW.png) –