patternMinor
Detecting palindromes in binary numbers using a finite state machine
Viewed 0 times
finitepalindromesnumbersbinaryusingstatemachinedetecting
Problem
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:
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
Here's an example of a pattern that detects a sequence of
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.
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:
- Maybe the binary sequence is a special type of palindrome that is regular? (I'm a little fuzzy on this)
- 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...01The 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.
Solution
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 th
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 th
Code Snippets
1 1 0 1
R 1 1 1 1 1 1 R
R 1 0 R0 1 0 0
R 0 0 0 0 0 0 R
R 1 0 RContext
StackExchange Computer Science Q#32081, answer score: 5
Revisions (0)
No revisions yet.