Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CISC 223 - Assignment 3 (Winter 2024)

Due: Thursday March 7, 2:00 PM

Regulations on assignments

• The assignments are graded according to the correctness, preciseness and legibility of the solutions. All handwritten parts, including figures, should be clear and legible. This assignment is marked out of 20 possible marks.

• Please submit your solution in onQ before the due time. The submission must be in one of formats: .PDF, .JPG, .PNG, .DOCX.

• Important: Assignments are evaluated based only on the files you submit in onQ. Please be careful that you submit the correct files and please verify your submission. Any additional material sent retroactively by email cannot be considered.

• The assignment must be based on individual work. Copying solutions from other students is a violation of academic integrity. See the course onQ site for more information.

1. (2 marks) Show that the following grammar is ambiguous:

S −→ aSbS | bSaS | ε

Here S is the start nonterminal and the set of terminals is {a, b}.

2. (4 marks) Design a deterministic pushdown automaton that recognizes the language

L = {akbic2k|i ≥ 0, k ≥ 1}

Draw a table that traces the behavior of your pushdown automaton on the input aacccc. The table should list the current state, currently remaining input, and current stack contents at each step of the computation (see examples on pages 217–218).

Note: Since the pushdown automaton has to be deterministic, we cannot use the general transformation that converts a grammar to a nondeterministic pushdown automaton (as discussed on pp. 218–219 in the text.)

3. Are the following languages context-free or non-context-free?

• If a language is context-free, give a context-free grammar that generates it.

• If a language is not context-free, prove this using the pumping lemma.

(a) (2.5 marks) A = {a2ib3ickdm|i ≥ k ≥ 1, m ≥ 1 }

(b) (2.5 marks) B = {aibkc2rd3m|i ≥ k ≥ 1, r ≥ m ≥ 1 }

4. Consider the context-free grammar with the following rules (S, X, Y are nonterminals, S is the start nonterminal and a, b, c are the terminals):

S → cY a | aY b | bX

X → bX | cXa | ε

Y → dY b | cX | ε

(a) (3 marks) Determine the sets FOLLOW(S), FOLLOW(X), FOLLOW(Y ), as well as the sets FIRST(α) where α is any of the right sides of the productions of the grammar.

For each element z belonging to a set FOLLOW(U), U ∈ {S, X, Y }, give a derivation starting from S of a string w where z occurs directly after U. If z is EOS, give a derivation starting from S of a string w where U is the last symbol of w.

(b) (2 marks) Does the grammar allow the use of recursive-descent parsing? Justify your answer – please be specific and give a detailed answer.

5. (4 marks) Use left-factoring and/or eliminate left-recursion to transform each of the below eight grammars into a form where the immediate problems preventing the use of recursive-descent parsing have been removed. As usual capital letters denote variables and lower case letters are terminals.

(a) S −→ abSc | abdSd | cbad | bdd | ε

(b) S −→ Sa | ba | Sdc | ε

(c) S −→ Scb | Sac | ab | Sdb | cba

(d) S −→ SA | ε

A −→ Ac | b

(e) S −→ bcbdSa | bcbcSb | cbSca | dbba | ε

(f) S −→ aacSb | cSb | aacbd | dcb | ε

(g) S −→ acbSd | bdadS | bdabS | acc | dba | ε

(h) S −→ Sba | Sbc | a | c | da

Hint for (h): Here after elimination of left recursion you need to use also left-factoring (or vice versa).