Register

Linear grammar

470 views
0 votes
0 votes

Please follow the attachment how can we prove that the given language is not linear please explain?

User Avatar

1 Answer

0 votes
0 votes
Given grammar is not linear

as when you try to right a grammar for this

there will be more than one non terminals on RHS

S-->aSbS | bSaS | $\epsilon$
thus making it non linear
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
Abbas Ahmad asked Nov 30, 2018
413 views
Self doubt about relation between regular and linear grammar
If a grammar G is both left linear as well as right linear then,what should be the case a) G is always not regular b) G may or may not be regular c) something else
If a grammar G is both left linear as well as right linear then,what should be the case a) G is always not regularb) G may or may not be regularc) something else
User Avatar
0 votes
0 votes
0 answers
2
Ajit J asked Nov 17, 2018
800 views
TOC_left linear grammar
User Avatar
0 votes
0 votes
2 answers
3
sandyoverflow asked Oct 20, 2018
1,926 views
Does ambiguity problem is decidable for regular grammar(right linear grammar)?
Does ambiguity problem is decidable in regular grammar(right linear grammar)?
Does ambiguity problem is decidable in regular grammar(right linear grammar)?
User Avatar
1 votes
1 votes
1 answer
4
sushmita asked Sep 16, 2018
690 views
conversion of right linear grammar to DFA
In converting right linear regular grammar to DFA how to determine the final states? Can anyone tell the procedure?
In converting right linear regular grammar to DFA how to determine the final states?Can anyone tell the procedure?
User Avatar
Link Copied!