Regular Language

Question

Is the given Grammer represent a regular language ?

S->AaB

A->aC | epsilon

B->aB | bB | epsilon

C->aCb | epsilon

Answer 1

S → A a B

A → aC | ∈

C → a C b | ∈

Now it look like,

1) when A ≠ ∈,   a  aⁿ . bⁿ . a. B , where n ≥ 0  ===> looking like CFL

what about B ?

B → a B | b B | ∈  ===> (a+b)^m , m ≥ 0

Finally, it is like a aⁿ . bⁿ . a (a+b)^m , m ≥ 0, n ≥ 0

===> we can convert it  a a (a+b)^m , m ≥ 0 , by taking always n=0

2) when A = ∈ ===> a. B ===> a. (a+b)^m , m ≥ 0

Total RE = a a (a+b)^m + a. (a+b)^m  = a. (a+b)^m , m ≥ 0

Comments

oh yes thnku for pointing it out

---

brother can you help me with creating the dfa for it

---

check this

Answer 2

No it is not.See if it is to be a regular language then it must be accepted by a FA.So there must exist one regular expression for the above grammar.There is no such regular expression for this grammar so it is not a regular language its is a CFL.There is a dependency of "a" if we have to print a "b" just before the starting terminal "a".For printing 1 b there should be 1+1 "a"s,similarly for n "b"s there must be n+1 "a"s.So its not a regular language.

 

 

P.S-correct me if i am wrong ty :-).

Comments

I don't understood wht u trying to say man. Of course above expression can't generate 'b' the minimum string is 'a'