1) Determine L₁ U L₂, L₁ L₂, L₁*, and L₂*, where L₁= {a^m bⁿ | m, n > 0} and L₂= {aⁿ bⁿ | n > 0}.

2) Give a regular grammar that generates the strings over (a, b, c} in which the as precede the bs, which in turn precede the cs. It is possible that there are no as, bs, or cs.

3) Consider the grammar G with production rules

S BSA | A

A aA |

B Bba I

Construction an equivalent essentially non-contracting grammar, i.e. there are no production rules of the form V , except S if in L(G)) and with a non-recursive start symbol. Hint: see section 4.2 and the examples.

4) Give a regular expression for the language L(G) where G is the grammar is question 3.

Need solutions for above problems: #1, #2, #3, and #4