edited by
604 views

2 Answers

5 votes
5 votes

It says |x| is square means length can be 1,4,9,16,25,36 and so on.

1. For sure it is not regular.

2. Now lets prove it is not CFL. As we know PDA has an extra memory stack which is used for comparison. But here there is no comparison required. Simply keep on pushing any length string onto the stack. It will accept all the strings whose size is a perfect square but cannot reject the string whose size is not a perfect square.

3.  We can give an algorithm which can count number os alphabets in a string. 

    if(perfect square)

{

   It is accepted

}

else rejected.

As we can say both Yes for yes instance and No for no instance of input, it is recursive.

 

0 votes
0 votes
It is CSL . Hence it is recursive also . So option b is right.

Related questions