[SOLVED] CSCI435-Assignment 4

Description

Q1. [20] For a given language L = {aⁿb²ⁿ | n ³ 0 is even}.

• [8] Give a CFG that accepts L.

S -> aaSbbbb | ε

• [6] Show the sequence of derivations for the acceptance of aaaabbbbbbbb by G in (1).

S -> aaSbbbb

-> aaaaSbbbbbbbb

-> aaaabbbbbbbb

• [6] Draw a derivation tree for aaaabbbbbbbb.

Q2. [30] Construct a CFG for the following languages where n, m, k ³ 0.

• [10] L1 = { aⁿbⁿ | n is a multiple of 3 }

(a³)^x(b³)^x

(aaa)^x(bbb)^x

S -> aaaSbbb | ε

• [10] L2= { aⁿb^mc^k | k = n+m }

= Aⁿb^mc^k

= aⁿb^mc^n+m

= aⁿb^mcⁿc^m

= ((aⁿcⁿ)/A) ((b^mc^m)/b)

S -> AB

A -> aAc | ε

B -> bBc | ε

• [10] L3 = { aⁿb^m | n = m –1 }

N = m – 1

N + 1 = m

= Aⁿbⁿ⁺¹

= (aⁿbⁿ)/x * b

S -> xb

X -> axb | ε

• [10, optional] L4 = { aⁿb^mc^k | n=m or m £ k }

N = m or m <= l

(aⁿbⁿ/u)(c^k/v)     or       (aⁿ/x) (b^mc^kc^k/y)

S -> UV | XY

U -> aUb | ε

V -> cV | ε

X -> aX | ε

Y -> bYc | c | bAc | ε

A -> cA | c

Q3. [10] Give the language L that is generated by the given grammar, in a formal expression.

S ® aaSbb | SS | l.

e.g.) L = { w Î {a, b}* | n_a(w) = 2n_b(w) }

L = (aa)* (bb)*

Because a and b are in pairs

Q4. [10] Find an s-grammar for L = {aⁿb²ⁿ | n ³ 2}.

1 – a and 2 – b’s

X, Y, Z

Start at S

AaSbbbb | ε l

S -> aS1

S1 -> aXYZ

X -> bY | aXYZ

Y -> b

Z -> b

 

Q5. [20] For a grammar G with the productions where G = ( {S, A, B}, {a, b}, S, P ) with productions

S ® AB | bbbB,              A ® b | Ab,       B ® a..

• [8] Show that the grammar G is ambiguous.

Because there are two separate trees, it shows that it is ambiguous

• [6] Give language L that is generated by G, L = L(G), in a formal expression (including a regular expression).

S -> AB | bbbB

A -> b | Ab   => bAb => b⁺ (at least one b)

B -> a..

AB => b_a..

S -> AB | bbba..

S -> b⁺a.. | bbba..

(b⁺+bbb)a..

• [6] Can you construct an unambiguous grammar that is equivalent to G? Otherwise, show that G is inherently ambiguous.

If we substitute “A” in “S” it equals

S -> b+ | bbbB

B-> a..

Thus being unambiguous because removing “A,” the ambiguous is removed.

 

Q6. [35] In the given grammar G, generate the simplified equivalent grammar by eliminating the following productions through (1) – (3).

G = ( {S, A, B, C}, {a, b},  S, P ) with productions

S ®bAA | bB,     A ® aA | aaC ,   B ® bbB | l,      C ® A

• [10] Eliminate the l-productions

S -> bAA | bB | b

A ->  aA | aaC

B ->  bbB | bb

C -> A

• [10] Eliminate the Unit-productions from (1)

S -> bAA | bB | b

A -> aA | aaC

B -> bbB | bb

• [10] Eliminate the useless productions (2), so that give the simplified equivalent grammar.

S -> bB | b

B -> bbB | bb

• [5] Give the language L that is generated by this grammar, L = L(G), in a formal expression (including a regular expression).

(bb)*b

Containing b’s of odd length

 

Q7. [15] Convert the given grammar into Chomsky Normal Form (CNF).

S ® AB | aB,      A ® abb | l ,      B ® bbA

 

Hint: Eliminate the l-productions and/or any unit-production prior to their conversion into CNF.

 

Removing λ productions

S -> AB | aB | B
A -> abb
B -> bbA | bb

Removing unit productions

S -> AB | aB | bbA | bb
A -> abb
B -> bbA | bb

Removing mixed rules

S -> AB | WB | VVA | VV
A -> WVV
B -> VVA | VV
W -> a
V -> b

Change to final CNF

S -> AB | WB | CA | VV
A -> WC
B -> CA | VV
W -> a
V -> b
C -> VV

 

Q8. [10] Convert the given grammar into Greibach normal form.

S ® aSb | ab | bb

S -> aST_b

S -> aT_b

S -> bT^b

T_b -> b

 

=> S -> aST_b | aT_b | bT_b

T_b -> b