1 Determine L1 U L2 L1 L2 L1 and L2 where L1 am bn m n 0 a

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 a’s precede the b’s, which in turn precede the c’s. It is possible that there are no a’s, b’s, or c’s.

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

Solution

2 answer)

Give a regular grammar that generates the strings over (a, b, c} in which the a’s precede the b’s, which in turn precede the c’s. It is possible that there are no a’s, b’s, or c’s.

as per the question we required to generate a regular expression a’s precede the b’s, which in turn precede the c’s.

abc but the required regular expression is a*b*c* because of the given constraints

It is possible that there are no a’s, b’s, or c’s.

the final answer is a*b*c*