TOC question from virtual gate

Question

Given answer: A
Please explain

Answer 1

Language is regular and regular expression is : bb*cb*b Complement of L = L(G') = (a+b)* - bb*cb*b

Comments

The form of the grammar looks like that of a context sensitive language as its RHS has terminal as well as non terminals. Then how is it regular. Please elaborate a bit..

---

@digvijay,  in both cases.

@sv_jan5

if a language is regular then it is cfl and csl too.  So we have CFG for it and CSG too.

---

No sir .. L and l' can't be same.

---

@digvijay G and G' are two different grammar (depending on the inclusion / exclusion of last production bA$\to$A).

L(G) and L(G') are two languages, they are not related as complement of each other.

---

What Grammars are u considering for G & G' .. And as i note these should be:

G:                                                                                 G' :                                                      

S -> bSb / AcA                                                               S -> bSb / AcA

Ab -> A , Ab -> b                                                            Ab -> A , Ab -> b

bA -> b                                                                          bA -> b , bA -> A

@praveen sir what do u say ?

---

Yes,  including bA $\to$A in G'

---

So, L(G) should be CFL & L(G') should be regular ??

---

Yes.

---

Praveen sir I can't understand and please explain how the L(G) is context free from the Context-Sensitive Productions ?

S -> bSb / AcA
Ab -> A , Ab -> b
bA -> b  

Please explain how to approach the solution ?

---

^^ try to find the strings derived from this.

Actually regular language can be written from context-free productions and from context sensitive productions too. whatever is regular language is also cfl and csl too.

---

should not the L(g) = regular  and the L(g') = cfl here  be answer here becoz for second grammar we can not write regular expression for it plzz explain if i am wrong

---

I think L(G)={b^m c b^n | m>=n} so it should be cfl (dcfl) and L(G’)=bb*cb*b so it should be regular. Hence correct option should be B. @Praveen sir please verify.