- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Here we will see how to make a Turing machine for language L = {WW^{r} |W belongs to {0, 1}}. So this represents a kind of language where we will use only two characters 0s and 1s. The w is a string and w^{r} is reverse of it. So if w = 10110, then w^{r} will be 01101. So the Turing machine will accept the string z = 1011001101.

To solve this, we will use this approach. First check the first symbol, if it’s 0 then replace it using y and if that is 1, then replace using x. Then go to the end of string. So last symbol is same as the first one. We replace it also by x or y depending on it. After that again come back to the position next to the symbol replace from the starting and repeat the same process that is mentioned above. We have to keep in mind that since w^{r} is reverse of w of both of them will have equal number of symbols. Every time replace a nth symbol from beginning of string, replace a corresponding nth symbol from the end.

- Related Questions & Answers
- Construct a Turing Machine for language L = {ww | w ∈ {0,1}}
- Construct a Turing Machine for language L = {0n1n2n | n≥1}
- Construct ∈-NFA of Regular Language L = 0(0+1)*1
- Construct a TM for the language L= {ww : w ∈ {0,1}}
- Design a push down automaton for L = {wwR | w ∈ {a, b}+}?
- Construct ∈-NFA of Regular Language L = (0+1)*(00+ 11)
- Construct a Turing Machine for L = {a^n b^n | n>=1}
- Construct a ∈-NFA for the language L = (a* + b*)
- Construct ∈-NFA of Regular Language L = (00)*1(11)*
- Construct a Turing machine for L = {aibjck | i*j = k; i, j, k ≥ 1}
- Construct a Turing machine for L = {aibjck | i< j< k; i ≥ 1}
- Construct a Turing machine for L = {aibjck | i>j>k; k ≥ 1}
- Construct Turing machine for subtraction
- Construct Turing machine for addition
- Construct Turing machine for L = {an bm a(n+m) - n,m≥1} in C++

Advertisements