in Theory of Computation
316 views
0 votes
0 votes
Construct a grammar for L={a^nb^n/m, n greater then equal to 0,m doesn't equal to n}
in Theory of Computation
by
316 views

1 Answer

0 votes
0 votes

S-> aSb| A | B

A-> aA | a

B-> bB | b

Question was written incorrect so i assumed question as {anbm|n,m$\geq$0 & n$\neq m$}

S-> $\varepsilon$ is not possible here.

what I did is break language in 3 parts

1) S-> aSb to give equal no of a's followed by equal number of b's

2) S->A so that string contain at least single a followed by 0 b's

3) S-> B so string contain at last single b followed by 0 a's

if string start with step 1 then it must follow either 2 or 3 to terminate

if it follow 2 then language will have a>b else if 3 is followed language will have a<b

edited by

1 comment

....thnx tesla
0
0

Related questions

1 vote
1 vote
1 answer
4