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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

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

- Regular
- Recursive but not context free
- Context Free but not regular
- None of the above

+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

0 votes

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 588
- Exam Queries 568
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,083 questions

53,206 answers

184,553 comments

70,426 users