The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

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
asked in Theory of Computation by Active (2.9k points)
edited by | 88 views

2 Answers

+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.


answered by Loyal (6.3k points)

@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 ?

0 votes
It is CSL . Hence it is recursive also . So option b is right.
answered by Boss (33.4k points)
CSL is recursive?

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


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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,083 questions
53,206 answers
70,426 users