Question

Specify a Turing machine with input alphabet Σ = {a, b} that recognizes the language L...

Specify a Turing machine with input alphabet Σ = {a, b} that recognizes the language L = { ww | w ∈ Σ ∗}. Is L decidable?

0 0
Add a comment Improve this question Transcribed image text
Answer #1

The approach behind the construction of this Turing machine is firstly finding the mid point and then doing matching.

For example the string abaaba should be accepted by this Turing machine and if it will be done than we can also state that the language is decidable because from one of the definition of the language decidability if we are able to construct a Turing machine which will able to accept and reject the string generated by the language then we can say language is decidable.

By a/X/R we means we are scanning first symbol a and converting it to the second symbol X and then moving right.

Notation :-
R - Right , L - Left , B - Blank
X , Y - variables used for conversion of a , b respectively.

qi , qf represent our initial and final states.

Therefore the language is decidable since we are able to construct the Turing machine and accept the string generated by this language.

Add a comment
Know the answer?
Add Answer to:
Specify a Turing machine with input alphabet Σ = {a, b} that recognizes the language L...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT