Assignment 5

1. Consider the language \(A\) consisting of all strings in \(a\) and \(b\) with at least as many \(a\)s as \(b\)s, and the language \(B\) consisting of strings in \(a\) and \(b\) with at most as many \(a\)s as \(b\)s. Show that these languages are context-free languages by constructing CFGs for them.
2. Construct a CFG for the language \(L=\{a^ib^jc^k \mid i=j\textrm{ or }j=k\}\).
3. Show by construction why:
   1. the union of two CFGs is a CFG.
   2. the Kleene star of a CFG is a CFG.
   3. the concatenation of two CFGs is a CFG.
4. For the three grammars in examples 1 and 2, and using the technique described in class/the notes/the book, construct equivalent grammars that are in Chomsky Normal Form.