Introduction to automata Peter Linz 6th edition Exercise 1.2

Question

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}

Answer 1

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 :)

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$.

---

Corrected, thanks :)

---

Correct L2 too :)

---

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?

---

?

n=0, m < n why would $a^0b^m$ be there?

---

m < n means m < 0. How will you address m < 0?

---

m can’t be less than 0, lol

$b^m$ means b concatenated m times, how can you concatenate -1 times

---

Exactly you can’t right but the question askes for it.

---

No it doesn’t, it only says what the condition should be, as no such string is possible we reject everything when n=0

---

I guess that should be it then.