[Solved]: Detecting palindromes in binary numbers using a finite state machine

Problem Detail: 

In my first algorithms class we're creating these patterns that are supposed to model a finite state machine. We were given a task to think if we can figure out a way to detect palindromes in binary sequences (no points if we do, it's just a food for thought).

I specifically asked the professor, knowing a little about CS and that palindromes aren't regular, and that a finite state machine can only detect a regular language. But his answer surprised me, since he said that it is indeed possible and that he thinks we should be able to come up with a sotluion.

This brings two questions:

1. Maybe the binary sequence is a special type of palindrome that is regular? (I'm a little fuzzy on this)
2. Or the technique we're using to represent the state machine is more powerful than I think.

In case it's 2), I'll try to explain how we're representing the problem.

Imagine a finite wall, which is supposed to be filled with a predefined types of tiles. Each tile has four colors

You can design any tile you want, and as many as you want, but there has to be a finite number of tiles. They can be arranged in a single row, or into multiple rows, but the topmost row has to always match against the 0 and 1 colors. The end colors of the wall also have to be defined ahead of time, and the tiles have to match those, and they also have to match the adjacent tiles.

Here's an example of a pattern that detects a sequence of 01010101...01

The question is, is this pattern more than just modeling a finite state machine? If not, how can I use this to detect palindromes?

Update: There has to be a finite number of tile designs, and the number of tiles has to be finite as well (the input will always be finite as well). As for the rows, there can be an arbitrary number of rows, the only condition is that the tiles on a second row must match in the top color with the tiles on the row above them. The number of colors isn't limited as well, though it can't be infinite.

Asked By : Jakub Arnold

Answered By : babou

In a nutshell: As presented, with a single row of tiles, the tiling system is equivalent to a finite state automaton. It cannot recognize the set of palindromes which is context-free, but not regular. However, if the tiling system is extended, allowing as many rows as needed (possibly with the addition of a column on each side), then it becomes as powerful as a linear bounded automaton, recognizing context-sensitive languages, and thus also palindromes. The last section is a simple set of tiles to recognize palindromes.

Recognizing palindromes with a single row of tiles

Regarding your tiling system, I am missing some details. Is the number of tiles finite, or just the number of different tile designs. More precisely, while the number of designs can be finite, i.e. the same for all sequences to be recognized, the number of tiles of each design should be sufficient in number, which may depend on the sequence to be recognized, though each recognition would use only a finite number of tiles.

If the number of tile is finite, less than some fixed number $n$ that is independent of the sequence to be recognized, you can at best recognize finite sets of sequences, which is much less than all regular languages.

Second point: is the number of different colors can be set at any value, the same for all sequences of the language to be recognized. If not you cannot recognize all regular languages.

If you have any number of tiles, finite number of designs, any number of colors, that is indeed equivalent to finite state automata, where the colors stand for the states, and the tiles stand for the transitions.

I am assuming you have only a single row of tiles, with the blue at bottom, as seems to be implied by your drawing.

I do wonder whether It helps understanding. Maybe so?

As you said, palindromes do not form a regular set. One disputable intuitive explanation is that palindrome recognition implies counting, and finite state machines cannot count. But there are formal ways of proving that.

The language of palindromes is actually a Context-Free (CF) language. Context-free languages are strictly a superclass to regular languages recognized with finite state automata. So any regular language is context-free, but the converse is false. For example the language of palindromes is CF but not regular.

Thus, palindromes cannot be recognized with a single row of tiles.

What more could be said.

Finite state automaton (FSA) is implicitely the name of a device that has only a finite number of states, used to control a reading head that read-input from left to right on a tape, without ever leaving the input string area, and never writes.

Finite state machines are usually considered as doing the same, except that some can also write on an output tape.

If we are not too attached to established terminology, we could try to relax some of these constraints, while keeping the finite number of states.

A first attempt could be to allow the head to move in any direction.

That gives you what is called a two-way finite state automata. They seem more powerful, but it can be proved that they do no more than FSA (whether deterministic or not).

Another possibility is to allow the automaton to overwrite the tape it is reading, but still without ever leaving the area that was occupied by the input string. This is called a linear bounded automaton (LBA). The LBA is actually one of the most powerful automata there is. They recognize all the context-sensitive (CS) languages, which include the CF languages.

The problem is that they are so powerful that they are difficult to control, analyze or use. But they will recognize palindromes with a finite number of states.

I have been excluding other type of automata which do have a finite number of state for control, but use unlimited memory, which one could perceive as having unbounded number of states.

Extending the tiling system

In FrankW's answer, it is shown that, by extending the tiling system with several rows, one can recognize palindromes. He has there a very interesting idea, which I am trying to push here.

It can be pushed further. If you allow an arbitrary number of rows, and add a column on each side, it seems that the tiles can actually mimic a linear bounded automaton. Hence, it becomes a very powerful computational system.

I am saying "it seems" because I did not go through all the tedious details of the construction, but only tried to convince myself.

However, rather than go through even the basic aspects of the construction, which are already complex, I will rely on existing results in automata theory.

A row of tiles may be seen as the configuration of a one-dimensional bounded cellular automaton (BCA). Columns represent the evolution of individual cells.

The colors of left and right sides of tiles represent the information exchanged between adjacent cells, while the top and bottom colors represent the state of the cells before and after transitions.

So it seems that a BCA can be simulated by the extended tiling system.

David Milgram showed in 1976 that BCA can simulate a LBA.

Hence the extended tiling system can simulate a LBA.

The extended tiling system is therefore a very powerful computational system, that can recognize context sensitive languages.

Hence the extended tiling system can recognize palindromes, among many other things.

Now, I am not giving you the details of the recipe to recognize palindromes and other things in this way, simply because it is very complicated, and no one would read it anyway, if I were able to write it without bugs.

A set of tiles to recognize palindromes

The general construction is far too complex to be used. However, here is a simple set of tiles to recognize palindromes on the alphabet $\{0,1\}$ as requested.

As one might expect it is symmetrical.

R and B stand for red and blue

Matching leftmost and rightmost symbol 1, and removing them

 1      1      0     1 R 1    1 1    1 1   1 R  R      1      0     R 

Matching leftmost and rightmost symbol 0, and removing them

 0      1      0     0 R 0    0 0    0 0   0 R  R      1      0     R 

Filling in the sides with fully red tiles

 R R R  R 

Creating the bottom line in blue

 R R R  B 

But this has nothing to do with finite state machines, as far as I can tell.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32081