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(n)-where rl is a regular expression or a characteristic function defining a regular language. Returns an FSM accepting L(rl). For example, FSM f = regLangtoFSM({w: |w| is odd}) CFGtoPDA(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

IF L is a CFL, the Pumping Lemma for CFLs tells us that for some integer n1, if sL and |s|n, then s can be written as

If some sL has length n|s|<2n, then L is infinite: for some u,v,w,x,y as in the Pumping Lemma, L then contains all strings uvkwxky for k0. Because at least one of v,x is nonempty, these strings are all distinct.

Conversely, suppose L is infinite. Then L contains strings of length n. Suppose sL has length |s|n. Then s=uvwxy as in the Pumping Lemma. If |s|2n, then we can "pump downward": s=uwy=uv0wx0yL is a strictly shorter string, which by 2. still has length |s|n. (|s|=|s||vx||s||vwx||s|nn.)

If s is still of length 2n then we can do it again, to obtain yet another, even shorter string s of length n. Eventually we obtain a string ¯s whose length is <2n and n.

One way of determining whether a given context-free grammar G produces an infinite language is this:

Find a grammar G+ with L(G+)=L(G) such that G has no rules on the form A or AB where A and B are any non-terminals. (Implication: for any derivation A_ we have |A|<|| unless is a single terminal.)

Find a grammar G with L(G)=L(G+) such that all non-terminals A derive some string and SA for some and and which also has the above property of G+.

Construct a graph with an edge from A to B whenever B occurs on the right-hand side of a rule AB.

( and are arbitrary strings of terminals and non-terminals.)

If the graph has a cycle, the language is infinite. Otherwise not.

Proof(ish):

From cycle to infinity: as a consequence of the properties of G+, any derivation AA implies ||>0. In other words, each trip through the cycle makes the sentential form longer, and also nothing will make it shorter. The cycle can be gone through as many times as you like, and by the properties of G the cycle can be reached from S and reaching it means you will eventually generate a string. Hence strings of an infinite number of different lengths can be generated. Strings of different lengths are different, hence the language has infinitely many strings.

From acyclic to finite: if there is no cycle, sort the non-terminals topologically. Let A be any non-terminal with no out-edges, i.e. all right-hand-sides of production rules consist only of strings of non-terminals. Replace every occurrence of A in some other right-hand side with the union of all strings A can generate (so if Aab and BAc then when done Bacbc) and remove A from the grammar. It will still be acyclic, but shorter by one non-terminal. Repeat this until it consists only of S, which will have non-recursive production rules, i.e. its rules will just be a finite list of strings the language can generate.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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