Given a CFG G, complete the pseudocode-style procedure that returns true if G ge

Question

Given a CFG G, complete the pseudocode-style procedure that returns true if G generates an infinite number of strings that end with ab, and false otherwise. You may use any of the algorithm and decision procedures presented in chapter 14, and you may find the ones below to be especially helpful: decideCFLInfinite(p) - where p is a PDA. Returns true if L(p) is infinite, and false otherwise. regLangtoFSM(r|) - where r| is a regular expression or a characteristic function defining a regular language. Returns an FSM accepting L(r|). For example, FSM f = regLangtoFSM({w: |w| is odd}) CFG to PDA(g) - where g is a CFG. Returns a PDA accepting L(g). intersectPDAandFSM (p, f) - where p is a PDA and f is an FSM. Returns a PDA accepting L(p) intersection L(f) boolean abEndingsInfinite (CFG G) { }

Explanation / Answer

Based on the help pointers:

boolean abEndingsInfinite(CFG G){

PDA PG = CFGtoPDA(G);

FSM Fendswith_ab = regLangtoFSM({w: w ends with ab});

PDA Pn =intersectPDAandFSM(PG , Fendswith_ab );

if (decideCFLInfinite(Pn))

return true;

else

return false;

}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.