Introduction to automata Peter Linz 6th edition Exercise 1.2
in Theory of Computation
99 views
0 votes
0 votes
Find grammar for the following languages.

L1 , L2 , L1L2 , L1 U L2

L1 = {a^n b^m : n>=0, m<n}

L2 = {a^3n b^2n, n>=2}
in Theory of Computation
by
5 points
99 views

1 Answer

0 votes
0 votes
For L1

$S\rightarrow aSb$

$S\rightarrow aA$

$A\rightarrow aA$

$A\rightarrow \epsilon$

For L2

$S\rightarrow aaaSbb$

$S\rightarrow aaaaaabbbb$

You can check for correctness :)
edited by
by
3.6k points

10 Comments

L1 will accept b but it should not be accepted as m < n so if n = 0 then m must be -1 or something. I think the question should be m <= n or n = 1.

For L2 the minimum string should be $a^6b^4$.
1
1
Corrected, thanks :)
0
0
Correct L2 too :)
1
1
I have just one doubt that is the minimum string that L1 will accept is a. But according to the question, it can be $a^0b^m$ where $m < 0$. How will you address that?
0
0
?

n=0, m < n why would $a^0b^m$ be there?
0
0
m < n means m < 0. How will you address m < 0?
0
0
m can’t be less than 0, lol

$b^m$ means b concatenated m times, how can you concatenate -1 times
0
0
Exactly you can’t right but the question askes for it.
0
0
No it doesn’t, it only says what the condition should be, as no such string is possible we reject everything when n=0
0
0
I guess that should be it then.
0
0
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.