88 views

If $L = \Bigl \{ x \mid x \in \{ a, b, c \}^*, \text{The length of$x$is a square } \Bigr \}$ then $L$ is

1. Regular
2. Recursive but not context free
3. Context Free but not regular
4. None of the above
edited | 88 views

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

@tusharp Can you please explain the working of halting turing machine here means how it will know whether length of a string is perfect square or not ?

It is CSL . Hence it is recursive also . So option b is right.
0
CSL is recursive?
+1

@aditi19 every CSL  is recursive, recursive might or might not be CSL.

0
can you pls explain how the above language is recursive or CSL?