1
$\begingroup$

I'm having trouble proving, or understanding why a two-head one-way finite memory machine could accept a non-regular language– for instance, $(w \mid w \in (a,b)^{*}, w= a^i b^i, i\geq 0)$.

For clarity, a two-head one-way finite memory machine works as follows – it has a finite control and a read-only input tape. The input tape contains a string, with a special blank symbol at the right end. The machine starts in the start state with both heads on the first symbol of the input string. In one step the machine reads the current symbols under the two read heads, moves one or both of the heads one position to the right, and changes state. Each step of the machine is uniquely determined by its current state and the symbols read by the two heads. (That is, the machine is deterministic.) The machine accepts the input string if it reaches an accepting state.

$\endgroup$
  • 1
    $\begingroup$ Suppose I gave you a string of text and asked you to determine if it was a palindrome. Think about how you, as a human being, might do that by pointing at characters with your index fingers. Then implement that algorithm as a machine. $\endgroup$ – David Richerby Oct 12 '16 at 7:48
  • $\begingroup$ That wouldn't satisfy the one-way restriction, though. $\endgroup$ – Klaus Draeger Jan 30 '17 at 14:34
7
$\begingroup$

Just a "visual" Hint :-D

H1: v
    A A A B B B $
H2: ^

H1:   v
    A A A B B B $
H2: ^

H1:     v
    A A A B B B $
H2: ^

H1:       v        // found "B" ... let's
    A A A B B B $  // count both sides
H2: ^

H1:         v
    A A A B B B $  // ... go on ...
H2:   ^

H1:           v
    A A A B B B $  // ... go on ...
H2:     ^

H1:             v
    A A A B B B $  // H1 is on $, H2 on (the first) B ...
H2:       ^
$\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.