Consider the language L1 a b i m n 0 Construct a context f

Consider the language L_1 = (a\" b\" i m. n > 0) Construct a context free grammar such that L(G) = L_1 Construct a regular grammar G such that L(G) = L_1 Consider the language L_2 = (a\" b\" i n > 0) Construct a context-free grammar G such that L(G) = L_x, Explain why there cannot exist a regular grammar G Such that L(G) = L_2 Determine L_1, U L_2 L, L_2 L_1*. and L_2*. where L_1 and L_2 are as defined above Give a regular grammar that generates ma strings over (a. b. c) in which the as precede the. which in turn precede the It is possible mat there are no a\'s. b\'s. or c\'s Consider the grammar G with production rules S rightarrow BSA I A A rightarrow aA| lambda 8 rightarrow Bba I lambda Construction an equivalent essentially non-contracting grammar. i.e., there are no production rules of the form V rightarrow lambda. except S rightarrow lambda if lambda in L(G)) and with a non-recursive start symbol Hint tee section 4 .2 and the examples Give a regular expression tor the language L(G) where G is the grammar is question 7.

Solution

2)
Languages generated by L(G) = {ambn |m > 0 and n > 0} are L = {aa*bb*}

Regular Grammar is ->

S -> a A
A -> aA | B
B -> b | bB

1)
Its a known fact that \"Every regular language L is also Context Free\".

Therefore the context free grammar for L(G) = {ambn |m > 0 and n > 0} is

S -> a A
A -> aA | B
B -> b | bB

3)
Languages generated by L(G) = { anbn | n > 0 } is equal number of a\'s and b\'s.

For example, L = {ab, aabb, aaaabbbb ...}

Context free Grammar is ->

S -> aSb
S -> ab

4)
Assume Regular grammar exists, and it has N states. What happens when the input string has N+1 a\'s in it, followed by N+1 b\'s?

Since the FA only has N states, we must visit some state sT twice on seeing N+1 a\'s.
The FA cannot know whether we are entering sT for the first time, when we\'ve seen i < N a\'s, or the second time, when we\'ve seen j > i a\'s.
There must be a path from sT to an accepting state, since the input string is in the language.
The FA will accept an input string without an equal number of zeros and ones, since i != j, and there is a path to an accepting state from sT on the remaining input.