Question

In: Computer Science

Theory of Computation Problem Let G be an arbitrary CFG (Context-free Grammer), and let DG be...

Theory of Computation Problem

Let G be an arbitrary CFG (Context-free Grammer), and let DG be the string-pushing PDA(pushdown automata) for it. Let w be some string of length n in L(G).

Suppose you know that the leftmost derivation of w in G consists of m substitutions. How many transitions would be in the corresponding computation of DG for input string w? Justify your answer carefully.

Solutions

Expert Solution

NPDAs

Construct non-deterministic pushdown automata to accept the following languages.

  1. {1n0n | n>0}
  2. {0n12n | n>=0}
  3. {1n0n | n>0} U {0n12n | n>=0}
  4. (0+1)* - {ww | w in {0,1}*} (complement of ww)

DPDAs

Construct deterministic pushdown automata to accept the following languages.

  1. {10n1n | n>0} U {110n12n | n>0}
  2. Binary strings tha contain an equal number of 1s and 0s.
  3. Binary strings with twice as many 1s as 0s.
  4. Binary strings that start and end with the same symbol and have the same number of 0s as 1s.

CFGs

Construct context free grammars to accept the following languages.

  1. (2.4b) {w | w starts and ends with the same symbol}

    S -> 0A0 | 1A1
    A -> 0A | 1A | e

  2. (2.4c) {w | |w| is odd}

    S -> 0A | 1
    A -> 0S | 1S | e

  3. (2.4d) {w | |w| is odd and its middle symbol is 0}

    S -> 0 | 0S0 | 0S1 | 1S0 | 1S1

  4. {0n1n | n>0} U {0n12n | n>0}

    S -> 0A1 | 0B11
    A -> 0A1 | e
    B -> 0B11 | e

  5. {0i1j2k | i!=j or j!=k}

    S -> AC | BC | DE | DF
    A -> 0 | 0A | 0A1
    B -> 1 | B1 | 0B1
    C -> 2 | 2C
    D -> 0 | 0D
    E -> 1 | 1E | 1E2
    F -> 2 | F2 | 1F2

  6. Binary strings with twice as many 1s as 0s.

    S -> e | 0S1S1S | 1S0S1S | 1S1S0S

Ambiguity

  1. Explain why the grammar below is ambiguous.

    S -> 0A | 1B
    A -> 0AA | 1S | 1
    B -> 1BB | 0S | 0

    The grammar is ambiguous because we can find strings which have multiple derivations:

    S
    0A
    0 0AA
    00 1S 1
    001 1B 1
    0011 0 1
    S
    0A
    0 0AA
    00 1 1S
    0011 0A
    00110 1
  2. (extra credit)
  3. Demonstrate that G is ambiguous.

    The ambiguity is primarly due to the following rules:

    • IF-THEN -> if condition then STMT
    • IF-THEN-ELSE -> if conditio n then STMT else STMT

    If we start with an IF-THEN statement and substitute an IF-THEN-ELSE for the consequent, we get:

    if condition then if condition then STMT else STMT

    However, if we start with an IF-THEN-ELSE clause and substitute an IF-THEN for the consequent, we get the same thing. So, it is ambiguous. Note that many real programming languages (such as C and Java) exhibit this exact ambiguity in their syntax.

  4. (extra credit)

5.Converting to Normal Form

  1. Put the following grammar into Chomsky Normal Form.

    S -> A | AB0 | A1A
    A -> A0 | e
    B -> B1 | BC
    C -> CB | CA | 1B

    Remove all e rules

    S -> e | A | AB0 | A1A | B0 | A1 | 1A
    A -> A0 | 0
    B -> B1 | BC
    C -> CB | CA | 1B

    Remove unit rules

    S -> e | A0 | 0 | AB0 | A1A | B0 | A1 | 1A
    A -> A0 | 0
    B -> B1 | BC
    C -> CB | CA | 1B

    Convert remaining rules into proper form

    S -> e | A0 | 0 | AS1 | B0 | A1 | 1A
    A -> A0 | 0
    B -> B1 | BC
    C -> CB | CA | 1B
    S1 -> B0 | 1A

    S -> e | AN0 | AS1 | BN0 | AN1 | N1A
    A -> AN0 | 0
    B -> BN1 | BC
    C -> CB | CA | N1B
    S1 -> BN0 | N1A
    N0 -> 0
    N1 -> 1

    NOTE: We did not need to create a new start state because the given one did not appear in the right side of any rule.

  2. Convert the following grammar into an equivalent one with no unit productions and no useless symbols.

    S -> A | CB
    A -> C | D
    B -> 1B | 1
    C -> 0C | 0
    D -> 2D | 2

    Converts to

    S -> 0C | 0 | 2D | 2 | CB
    A -> C | D
    B -> 1B | 1
    C -> 0C | 0
    D -> 2D | 2

    A is now useless and can be removed.

6. Derivations in Chomsky Normal Form

  1. (2.19) Show that if G is a CFG in Chomsky normal form, then for any string w in L(G) of length n>=1, exactly 2n-1 steps are required for any derivation of w.

    We begin with a single nonterminal ("S") and form the string by making substitutions according to the rules. Each rule of the form A->BC adds a new nonterminal, and each rule of the form A->a converts one nonterminal into a terminal. Since it takes n-1 steps to grow our string from the original nonterminal to n nonterminals, and then n steps to convert each of those nonterminals into terminals, it takes 2n-1 steps to derive a string of length n.

  2. (2.20) Let G be a CFG in Chomsky normal from tha t contains b variables. Show that if G generates some string using a derivation with at least 2b steps, then L(G) is infinite.

    L(G) is infinite if any nonterminal shows up in a reduction of itself because this indicates a loop in the grammar. In the largest possible derivation, starting with the start variable ("S") we replace it with two other variables and each of those are replaced with two other variables and so on. Since no variable can be repeated along any branch of the tree without creating a cycle, the tree will be depth b and will contain 2b-1 nodes. So, if a derivation requires 2b or more steps, the grammar must contain a cycle and L(G) must be infinite.

7.Two Way PDAs

Show that the set {0n1n0n | n>0} is accepted by a 2-way PDA.

This 2-way PDA works by moving right across the string to make sure it begins with 0n1n. Then it moves left to the beginning of the 1s and continues to the right to check for 1n0n.


Related Solutions

Let G = (AN , AT , S, P) be a context-free grammar in Chomsky normal...
Let G = (AN , AT , S, P) be a context-free grammar in Chomsky normal form. Prove that if there exists a word w ∈ L(G) generated by a derivation that uses more than |P| + |AT | steps, then L(G) is infinite.
Let S ⊆ R and let G be an arbitrary isometry of R . Prove that...
Let S ⊆ R and let G be an arbitrary isometry of R . Prove that the symmetry group of G(S) is isomorphic to the symmetry group of S. Hint: If F is a symmetry of S, what is the corresponding symmetry of G(S)?
Let f: X-->Y and g: Y-->Z be arbitrary maps of sets (a) Show that if f...
Let f: X-->Y and g: Y-->Z be arbitrary maps of sets (a) Show that if f and g are injective then so is the composition g o f (b) Show that if f and g are surjective then so is the composition g o f (c) Show that if f and g are bijective then so is the composition g o f and (g o f)^-1 = g ^ -1 o f ^ -1 (d) Show that f: X-->Y is...
Prove that if G is a context-free grammar in which every variable occurs on the left...
Prove that if G is a context-free grammar in which every variable occurs on the left side of at most one production, then G is unambiguous.
Consider the context-free grammar G = ( {S}, {a, b}, S, P) where P = {...
Consider the context-free grammar G = ( {S}, {a, b}, S, P) where P = { S -> aaSb | aab }. Construct a NPDA M that such that L(M) = L(G). I would like the transition graph for this NPDA please.
Consider the following context-free grammar G: E ® T + E ® * T i E...
Consider the following context-free grammar G: E ® T + E ® * T i E ® f i E ® * f + T ® + Questions: (5 points) Compute the Canonical LR(1) Closure set for state I0 for grammar G. (10 points) Compute (draw) the DFA that recognizes the Canonical LR(1) sets of items for grammar G. (5 points) Construct the corresponding Canonical LR(1) parsing table. (10 points) Compute (draw) the DFA for LALR(1). (5 points) Construct LALR(1)...
Graph Theory: Let S be a set of three pairwise-nonadjacent edges in a 3-connected graph G....
Graph Theory: Let S be a set of three pairwise-nonadjacent edges in a 3-connected graph G. Show that there is a cycle in G containing all three edges of S unless S is an edge-cut of G
Problem 6-15 Expectations Theory Assume that the real risk-free rate is 2.5% and that the maturity...
Problem 6-15 Expectations Theory Assume that the real risk-free rate is 2.5% and that the maturity risk premium is zero. Also assume that the 1-year Treasury bond yield is 5.8% and a 2-year bond yields 6.4%. What is the 1-year interest rate that is expected for Year 2? Round your answer to two decimal places. _______% What inflation rate is expected during Year 2? Round your answer to two decimal places. ______% Comment on why the average interest rate during...
Can someone please answer these 3 by Friday? Problem 2 Let D, E, F, G, and...
Can someone please answer these 3 by Friday? Problem 2 Let D, E, F, G, and H be events such that P(D) = 0.7, P(E) = 0.6, P(F) = 0.8, P(G) = 0.9, and P(H) = 0.5. Suppose that Dc, E, Fc, Gc, and H are independent. (a) Find the probability that all of the events D, E, F, G, and H occur. (b) Find the probability that at least one of the events D, E, F, G, and H...
Algorithm problem 7 [Problem3-4] Let ƒ(n) and g(n) be asymptotically positive functions. Prove or disprove each...
Algorithm problem 7 [Problem3-4] Let ƒ(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures. e ƒ(n)∈O((ƒ(n))^2). f ƒ(n)∈O(g(n)) implies g(n)∈Ω(ƒ(n)). g ƒ(n)∈Θ(ƒ(n/2)). h ƒ(n)+ o(ƒ(n))∈Θ(ƒ(n)).
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT