Automata

Question

https://gateoverflow.in/?qa=blob&qa_blobid=5795855353278664308

Comments

I think it is accepted by NPDA.

---

this is regular Grammer given in ans

But i dont know how they said it as regular

---

I think it should be CSL. TM would accept the language.

It cannot be be accepted by NPDA because the sequence aren't confirmed here.

The language is different from ww^R , w belongs to (a+b)* which is accepted by NPDA.

---

@Shamim Ahmed why is it different from ww^R , w belongs to (a+b)* ?

Answer 1

L={$\epsilon$,a,b,ab,ba,aa,bb,..}

Trying to generate every string by using the condition

For example assume string aa  X=$\epsilon$ and Y=aa===> na(X)=0 and nb(y)=0  which is equal so it can be in the language. Similarly we can do this for any string. so L=$(a+b)^*$  which is regular.

Correct me if I'm wrong

Comments

Considering a language XY where X = aaababb Y=bbaaaabab,

Question says Na(X)=Nb(Y), Here string comparison is absolutely required.

Can we draw a DFA for this ??

---

It is $(a+b)^*$ DFA will be a single state which is intial aswell as final

---

@Hemanth_13

We have 4 a's in X and 4 b's in Y. They are mandatory in the string, and for them we need different states.

(a+b)* can also give us ϵ  right? ϵ  is not there in our language.  It would miss our 4 a's and b's. Hence this can't satisfy a DFA.

The language for this would be aaa(a+b)*a(a+b)* + bb(a+b)*b(a+b)*b.

Of course we can construct a DFA for the above case. But in the worst case string comparison cant be satisfied by DFA.

 

Answer 2

Regular Languages does not have memory element and so the language is not regular as it is counting number of X equal to the number of Y.Memory Element is needed to keep track of count.

It is neither regular nor CFL(how will the PDA know when the string of X ended and string of Y started).

It can be accepted by Turing machine and Hence ,CSL.