0
$\begingroup$

Can anyone help :(

L = {ww^r | w element of (0,1)*}

Would it be like in :pseudo code, check if the string is equal to itself in reverse?

$\endgroup$
  • $\begingroup$ StackOverflow is not a code-writing service. Please read through the Help Center, in particular How do I ask a good question? If you run into a specific problem, research it thoroughly, search thoroughly here, and if you're still stuck post your code and a description of the problem. Also, remember to include Minimum, Complete, Verifiable Example. People will be glad to help $\endgroup$ – Andreas Nov 29 '19 at 3:15
1
$\begingroup$

This can be done with a PDA or a TM. I'll assume you need a deterministic TM, for what I'm assuming is homework.

The strategy is to find the length of the string to determine where the middle is, then treat the tape as a stack to see if all of the characters match before and after that midpoint.

Here's an algorithm that can do it:

  1. For every two input characters you read until you hit #, write a 0 after the last #. This will keep track of where the "middle" is. Mark the inputs as you read them.
  2. If you hit # where you expected to find a number, the string length is odd, and so the machine can halt and reject.
  3. Otherwise, write another # after your string of zeros.
  4. Unmark all inputs and move the read head to the second #.
  5. Using the number of zeros you have, mark the right half of the input.
  6. Starting in the middle, working your way out, mark the left character and unmark the right if they match.
  7. If you encounter a pair that doesn't match, halt and reject.
  8. If you get all of the way to the #s, halt and accept.

For example, let's look at input #101100# (# here means the edges of the input). The read head is at the first #.

  1. Input starts as # 1 0 1 1 0 0 # (leaving room for markers)
  2. Mark the first two inputs, write a 0 at the end: # 1'0'1 1 0 0 # 0
  3. Mark the next two inputs, write a 0 at the end: # 1'0'1'1'0 0 # 0 0
  4. Mark the next two inputs, write a 0 at the end: # 1'0'1'1'0'0'# 0 0 0
  5. You've found the second #, so the string is of even length. Write a # at the end: # 1'0'1'1'0'0'# 0 0 0 #
  6. Unmark everything: # 1 0 1 1 0 0 # 0 0 0 #
  7. Now, starting from the second #, mark the inputs from the right, and the 0s from the left until all of the 0s are marked:
  8. First iteration: # 1 0 1 1 0 0'# 0'0 0 #
  9. Second: # 1 0 1 1 0'0'# 0'0'0 #
  10. Third: # 1 0 1 1'0'0'# 0'0'0'#
  11. You now know the midpoint of the string (it's where an unmarked input is to the left of a marked input).
  12. Starting from that midpoint, mark the left and unmark the right if they match: # 1 0 1'1 0'0'# 0'0'0'#
  13. Continue working outward, comparing in this way: # 1 0'1'1 0 0'# 0'0'0'#
  14. On the third step, we find that 1 and 0 don't match. Halt and reject.

I'll leave it as an exercise to you to determine how to convert this algorithm into a TM.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.