Homework Assignment 3:

COMP 455: Models and languages of Computation

DEADLINE: 11:59 P.M., Wednesday, Oct 16, 2024

Problem 1: (16 points; 4 parts) Design CFGs for the following languages. Follow the format presented in the class for specifying CFGs.

1.1 (4 points) L consists of all the strings over the alphabet {0, 1} which contain at least three 0’s or at least two 1’s.

1.2 (4 points) L = {w010w ′ | w, w′ ∈ {0, 1}*and |w| = |w ′ |}

1.3 (4 points) L is the language over the alphabet {a, b, c} given by L = {a i b j c k | i = j ri = k, and i, j, k ≥ 1}.

1.4 (4 points) The alphabet is {a, b, c, d} and L = {a nb mc md n | n, m ≥ 0}

Problem 2: (10 points; 4 parts) Let w = (())()(). Consider the grammar:

S → SS | (S) | ()

2.1 (4 points) Construct a parse tree whose yield is w.

2.2 (2 points) Give the leftmost derivation of w using your parse tree.

2.3 (2 points) Give the rightmost derivation of w using your parse tree.

2.4 (2 points) Give a derivation of w that is neither the leftmost nor the rightmost derivation.

Problem 3: (4 points; 1 part) Consider the CFG G = ({S, A}, {0, 1}, P, S) with P being:

S → AS | ϵ

            A → A0 | 1A0 | 10

This grammar is known to be ambiguous. Exhibit a string and two different parse trees for the string.

Problem 4: (10 points; 4 parts)

Consider the PDA in the above figure. It accepts using final states.

4.1 (4 points) Using IDs (instantaneous descriptions) derive a successful execution sequence using which the PDA accepts the string 1011000.

Diagram repeated for convenience

4.2 (2 points) Is the string 110 accepted by this PDA? if your answer is yes, show a successful execution sequence using IDs. If your answer is no then show that all executions sequences get stuck before finishing to read the string or end in a non-accepting state after processing string.

4.3 (2 points) Describe in informal terms the language recognized by this PDA.

4.4 (2 points) Convert this PDA into an equivalent PDA that accepts using the empty stack criterion. Show the transition diagram of this PDA.

Problem 5: (8 points; 2 parts) Consider the CFG (V, T, P, S) where V = {S, A, B}, T = {0, 1}, and P is as follows:

S → AS | A

       A → 0A | 1B | 1

B → 0B | 0

5.1 (4 points) Construct a PDA that accepts—via empty stack—the language generated by the above CFG. You must use the procedure shown in the class. Show the transition diagram of this PDA.

5.2 (4 points) Show also your PDA in the 7-tuple form. Clearly list each component of your 7-tuple.