Concatenation: REG / REC / DCFL / CFL?

Question

Let A is the language where no of 'a' is greater than no of 'b' and B is the language where no of 'b' is greater than no of ‘a’ the language A.B is ______________

a. Regular

b. DCFL but not Regular

c. CFL but not DCFL

d. REC but not DCFL

Comments

CFL but not DCFL?

---

Ans is given as Regular

---

it will be, CFL but not DCFL

---

It can be DCFL but not regular, right?

Every string will be like $\left \{ a^nb^0b^{n+p}a^q | n>0\ and\ p+n>q \right \}$ We know $p > q$ which implies $ n+p $ will be greater than q. We can change the state when we encounter first $b$ and again at first of second $a$.

 

But, it can't be regular since we are unable to remove counting. we have to ensure second $a$ is less than $b$

Answer 1

Yes Regular is correct answer.

consider any string you can divide it as two parts as given in question as(A is the language where no of 'a' is greater than no of 'b' and B is the language where no of 'b' is greater than no of ‘a’ the language A.B).

Ex: abaabba

divide as abaa and bba then the given condition satisfies.

2. abba

divide it as 'a' and 'bba' .

3. aaaab

divide it as aaaa and b.

Answer 2

Option C

It is not regular because in question requires comparison

Concatenation followed by both CFL and REC BUT if it is CFL then also rec