CSCI435 Home Assignment 4 Solved

35.00 $ 17.50 $

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . zip solution files instantly, after Payment

Description

5/5 - (1 vote)

Q1. For a given language L = {anb2n | n ³ 0 is even}.

  • [8] Give a CFG that accepts L.
  • [6] Show the sequence of derivations for the acceptance of aaaabbbbbbbb by G in (1).
  • [6] Draw a derivation tree for aaaabbbbbbbb.

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

  • [10] L1 = { anbn | n is a multiple of 3 }
  • [10] L2= { anbmck | k = n+m }
  • [10] L3 = { anbm | n = m –1 }
  • [10, optional] L4 = { anbmck | n=m or m £ k }

Q3. 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}* | na(w) = 2nb(w) }

Q4. Find an s-grammar for L = {anb2n | n ³ 2}.

Q5.  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..

  •  Show that the grammar G is ambiguous.
  •  Give language L that is generated by G, L = L(G), in a formal expression (including a regular expression).
  • Can you construct an unambiguous grammar that is equivalent to G? Otherwise, show that G is inherently ambiguous.

Q6.  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

  •  Eliminate the l-productions
  •  Eliminate the Unit-productions from (1)
  •  Eliminate the useless productions (2), so that give the simplified equivalent grammar.
  • Give the language L that is generated by this grammar, L = L(G), in a formal expression (including a regular expression).

 

Q7.  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.

 

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

S ® aSb | ab | bb

 

 

  • HW4-xxdnyu.zip