6
$\begingroup$

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

tile

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

wall

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.

$\endgroup$
  • $\begingroup$ The constructs given in both answers can always work with a finite number of tiles. The question is whether enough will be supplied. The issue is whether this finite number is fixed or depends on the sequence to be recognized. If you say that the number of tiles is finite, how do we know we have enough tiles of the right design? But I should probably have said bounded rather than finite. So my question is whether we get any finite number of tiles of needed design for each computation. $\endgroup$ – babou Oct 19 '14 at 18:26
  • $\begingroup$ The computational model you are studying is actually known as Wang Tiles. $\endgroup$ – Hendrik Jan Oct 19 '14 at 18:37
  • $\begingroup$ Now that I undertand (I hope) what you want, I have added a simple set of tiles to recognize palindromes. But I do not see the connection with finite state machines ... or is it with cellular automata? $\endgroup$ – babou Oct 19 '14 at 20:51
  • $\begingroup$ @babou thanks for such a great answer! I guess it doesn't have anything to do with finite state machines after all, that was just my initial guess. $\endgroup$ – Jakub Arnold Oct 21 '14 at 0:20
  • $\begingroup$ In a cellular automaton, each state is a finite state device. But you have many cells. If you can grow the number of cells, then this finiteness is only illusion. Without growth, you can till get out of FSA realm. $\endgroup$ – babou Oct 21 '14 at 6:11
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great observation about BCA. I also believe, this should work. One nitpick about your "nutshell": If a language is context-free, that does not exclude the possibilty of it being regular. You should write "context-free, but not regular" or something along these lines. $\endgroup$ – FrankW Oct 19 '14 at 16:33
  • $\begingroup$ @FrankW Thanks. Was started by your idea. regarding "nutshel", I was actually careful in the text, but maybe too brief in the abstract. It seems that other than reading each other, we interest no one (vote-wise at least). I will amend my nutshell, as I have a bunch of typos to correct too. Regarding BCA, the idea came as I was struggling through a direct construction, somewhat painful. Probably helped get the flash. I did not know the 1976 result, but it seemed plausible, and a quick search ... Maybe the universe is made of square tiles of all colors. Nice. $\endgroup$ – babou Oct 19 '14 at 16:45
4
$\begingroup$

The model is more powerful than finite state machines.

If you only allow a single row, you can already simulate a FSM (without $\epsilon$-transitions, but that doesn't restrict their power) by having colors for the states, and tiles for each possible transition:

From the left state on reading the top symbol you go to the right state. (Bottom field is not used and can be filled with any color.)

By using more than one row, we can e.g. add a simple stack:

For each stack symbol $s$, add three colors $s$, $s_+$, and $s_-$, also add a neutral color $n$.

Each row of the pattern describes one place in the stack. The color in the right resp. left fields between two symbols of input describes the symbol in the respective cell at that point of the computation. (It's one of the colors $s$, or $n$ if the cell is empty.)

For the tiles in the top row we use the same basic design as for the FSM, but in the bottom field add one of the symbols $s$, $s_+$, or $s_-$. $s_+$ is interpreted as "add $s$ to the top of the stack", $s_-$ as "remove $s$ from the top of the stack" and $s$ as "$s$ is required to be top of the stack and remains there".

Furthermore we need tiles that manage the stack. There are again three types:

  • $s_+$ on top, $s$ on the right, $t_+$ on the bottom, and $t$ on the left.
  • $s_-$ on top. $s$ on the left, $t_-$ on the bottom, and $t$ on the right.
  • $s$ on the top, left, and right, $t$ on the bottom.

For each of these types, $t$, $t_+$, and $t_-$ many be replaced with $n$ to indicate the bottom of the stack. Also we have all-$n$-tilese to fill the bottom of the pattern below the stack.

Note that this automaton does not have the full power of a PDA, but it is capable of accepting the language of palindromes. I'll leave it to you to construct the specific instance.

$\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.