CS 341 Homework 15Parsing1. Show that the following languages are deterministic context free. (a) {ambn : m n} (b) {wcwR : w {a, b}*} (c) {cambm : m 0} {damb2m : m 0} (d) (amcbm : m 0} {amdb2m : m 0}2. Consider the context-free grammar: G = (V, , R, S), where V = {(, ), ., a, S, A}, = {(, ), .}, and R = { S (), S a, S (A), A S, A A.S} (If you are familiar with the programming language LISP, notice that L(G) contains all atoms and lists, where the symbol a stands for any non-null atom.) (a) Apply left factoring and the rule for getting rid of left recursion to G. Let G' be the resulting grammar. Argue that G' is LL(1). Construct a deterministic pushdown automaton M that accepts L(G)$ by doing a top down parse. Study the computation of M on the string ((()).a). (b) Repeat Part (a) for the grammar resulting from G if one replaces the first rule by A . (c) Repeat Part (a) for the grammar resulting from G if one replaces the last rule by A S.A.3. Answer each of the following questions True or False. If you choose false, you should be able to state a counterexample. (a) If a language L can be described by a regular expression, we can be sure it is a context-free language. (b) If a language L cannot be described by a regular expression, we can be sure it is not a context-free language. (c) If L is generated by a context-free grammar, then L cannot be regular. (d) If there is no pushdown automaton accepting L, then L cannot be regular. (e) If L is accepted by a nondeterministic finite automaton, then there is some deterministic PDA accepting L. (f) If L is accepted by a deterministic PDA, then L' (the complement of L) must be regular. (g) If L is accepted by a deterministic PDA, then L' must be context free. (h) If, for a given L in {a, b}*, there exist x, y, z, such that y and xynz L for all n 0, then L must be regular. (i) If, for a given L in {a, b}*, there do not exist u, v, x, y, z such that |vy| 1 and uvnxynz L for all n 0, thenL cannot be regular. (j) If L is regular and L = L1 L2 for some L1 and L2, then at least one of L1 and L2 must be regular. (k) If L is context free and L = L1L2 for some L1 and L2, then L1 and L2 must both be context free. (l) If L is context free, then L* must be regular. (m) If L is an infinite context-free language, then in any context-free grammar generating L there exists at least one recursive rule. (n) If L is an infinite context-free language, then there is some context-free grammar generating L that has no rule of the form A B, where A and B are nonterminal symbols. (o) Every context-free grammar can be converted into an equivalent regular grammar. (p) Given a context-free grammar generating L, every string in L has a right-most derivation.4. Recall problem 4 from Homework 12. It asked you to consider the following grammar for a language L (the start symbol is S; the alphabets are implicit in the rules):S SS | AAA | A aA | Aa | b (a) It is not possible to convert this grammar to an equivalent one in Chomsky Normal Form. Why not? (b) Modify the grammar as little as possible so that it generates L - . Now convert this new grammar to Chomsky Normal Form. Is the resulting grammar still ambiguous? Why or why not? (c) From either the original grammar for L - or the one in Chomsky Normal Form, construct a PDA that accepts L - .Homework 15 Parsing 15. Consider the following language : L = {wRw" : w {a, b}* and w" indicates w with each occurrence of a replaced by b, and vice versa}. In Homework 12, problem 5, you wrote a context-free grammar for L. Then, in Homework 13, problem 3, you wrote a PDA M that accepts L and traced one of its computations. Now decide whether you think L is deterministic context free. Defend your answer.6. Convert the following grammar for arithmetic expressions to Chomsky Normal Form:E E + TE TT T * FT FF (E)F id7. Again, consider the grammar for arithmetic expressions given in Problem 6. Walk through the process of doing atop down parse of the following strings using that grammar. Point out the places where a decision has to be made about what to do.(a) id * id + id(b) id * id * idSolutions 1. (a) L = {ambn : m n}. To show that a language L is deterministic context free, we need to show a deterministic PDA that accepts L$. We did that for L = {ambn : m n} in class. (See Lecture Notes 14). (b) L = {wcwR : w {a, b}*}. In class (again see Lecture Notes 14), we built a deterministic PDA to accept L = {wcwR : w {a, b}*}. It’s easy to turn it into a deterministic PDA that accepts L$. (c) L = {cambm : m 0} {damb2m : m 0}. Often it’s hard to build a deterministic PDA for a language that is formed by taking the union of two other languages. For example, {ambm : m 0} {amb2m : m 0} would be hard (in fact it’s impossible) because we have no way of knowing, until we run out of b’s, whether we’re expecting two b’s for each a or just one. However, {cambm : m 0} {damb2m : m 0} is actually quite easy. Every string starts with a c or a d. If it’s a c, then we know to look for one b for each a; if it’s a d, then we know to look for two. So the first thing we do is to start our machine like this:1 c0 d2The machine that starts in state 1 is our classic machine for anbn, except of course that it must have a final transition on $ to its final state.We have two choices for the machine that starts in state 2. It can either push one a for every a it sees, and then pop an a for every pair of b’s, or it can push two a’s for every a it sees, and then pop one a for every b. (d) L = (amcbm : m 0} {amdb2m : m 0}. Now we’ve got another unioned language. But this time we don’t get a clue from the first character which part of the language we’re dealing with. That turns out to be okay …
View Full Document
Unlocking...