Let $C$ be an infinite set of characters. I'd like an abstract machine which can recognize sequences consisting of $k$ (constant) of repetitions of a char from $C$.

For example, if ${x,y,z} \subset C$, and $k = 3$, it should recognize $xxx$ but not $ddd$ or $xyz$. (The same char must be repeated.)

Since $C$ is infinite, a finite state machine cannot recognize this. A Turing machine trivially can. But we don't anything like the power of a Turing machine; simply extending the FSM with a single register that points to a member of $C$ is enough.

My question is: What's the simplest formal abstract machine that is powerful enough to recognize this? Is there a standard extension to FSM's that enables them to recognize this? If I have more complicated versions of this machine (e.g. Move from state 2 to state 3 if you encounter a $k$ repetition of a $C$ char), what's the best way to express them?

  • 3
    $\begingroup$ Infinite alphabets are very problematic from a language- and automata-theoretic standpoint. Basically, though, what you need to handle this is something like set descriptors on transitions (I'd hesitate to even call these things languages). So you might label a transition $\{\gamma \gamma \mid \gamma \in \Gamma \}$, where $\Gamma$ is your "alphabet". Of course, then, there's no effective procedure for determining that you ought to take this transition, even though you and I know you would. $\endgroup$ – Patrick87 Oct 23 '13 at 13:42
  • 2
    $\begingroup$ Your question is too imprecise. Since there are apparently letters outside $C$, what is the alphabet $A$ containing $C$? And more importantly, how are $C$ and $A$ given? Are they countable? $\endgroup$ – J.-E. Pin Oct 23 '13 at 18:30
  • $\begingroup$ How can a Turing machine "trivially" recognise this language? Turing machines have finite alphabets so you'll need some kind of coding. $\endgroup$ – David Richerby Oct 23 '13 at 23:10

There is a generalization of NFAs in which the transitions are labeled with regular expressions. (They are equivalent to NFAs and DFAs.) You can represent "twice the same letter" by $\sum_{\sigma \in \Sigma} \sigma^2$. Of course, such expressions are not standard, but if you want a succinct representation, this is one.

| cite | improve this answer | |
  • $\begingroup$ Yuval - to clarify, the first big sigma means addition, i.e. selection, and the second one means the alphabet set. Yes? $\endgroup$ – SRobertJames Oct 24 '13 at 0:04
  • $\begingroup$ Right. I didn't notice this unfortunate clash of symbols... $\endgroup$ – Yuval Filmus Oct 24 '13 at 1:54
  • $\begingroup$ Another good reason to use $A$ for the Alphabet. :=) $\endgroup$ – J.-E. Pin Oct 24 '13 at 8:54

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.