If in a particular DFA , we are looping in a state for n symbols.... Is there any way to keep track of this 'n'?

  • 1
    $\begingroup$ Do you mean in an implementation? When you code it up you can keep track of whatever you want. The automaton itself, the formal construct, can not keep track of that, no. $\endgroup$ – Raphael Oct 18 '16 at 10:03
  • 1
    $\begingroup$ @Rapael The question is (to my eyes at least) how would adding this ability change the power of DFA? If it doesn't, then we might as well say DFA can count. In order to answer this you need to define exactly what you mean by adding a counter, for reasonable definitions you will probably have more expressive power then the "simple" DFA. There is a very good discussion in this question cs.stackexchange.com/questions/11155/can-an-fsa-count (also duplicate). $\endgroup$ – Ariel Oct 18 '16 at 10:07
  • 1
    $\begingroup$ What does keeping track of $n$ entail for you? What kind of finite state automaton do you envision? Can you give an example? Can you give a formal description? $\endgroup$ – Yuval Filmus Oct 18 '16 at 10:56
  • $\begingroup$ @Raphael.... In implementation..... To make it more precise let me explain... At one stage my DFA is in state q1. On input 'k' it remains in the state... I need put one threashhold value for 'k' such that when k exceeds a limit the machine should abort( or move to another state) Is this possible? and is it allowed in DFA , theoretically.... $\endgroup$ – ntn Oct 19 '16 at 7:04
  • $\begingroup$ If $k$ is finite and fixed, FAs can do that (not nicely, but well). See the question Ariel links. If $k$ is part of the input, nope; it's easy to come up with examples of non-regular languages you can accept then. That said, what do you care? You can do whatever you please in the implementation. $\endgroup$ – Raphael Oct 19 '16 at 7:57

First of all, let me mention that the definition of DFA is final. The definition specifies everything that counts as a DFA. If you modify the model, it is no longer a DFA. However, your question makes sense if we interpret it as trying to change the model while keeping the class of languages accepted by the model.

There are several ways to interpret counting. If you could keep track of the number of loops through a state and then still remember it when you exit the state, then (depending on your exact rules) you could accept the language $a^n b^n$. So any mechanism that allows this is ruled out.

Another interpretation is that the state keeps a loop counter $C$, and it can base its decisions on the value of $C$ (that is, allow the transition function to depend on the auxiliary information $C$). This is also too powerful – you can accept every unary language (i.e., a language over $\{0\}$) using this mechanism.

What if we just allow the state to remember some information about $L$? Say that we partition $\mathbb{N}$ (the natural numbers) into finitely many sets $S_1,\ldots,S_d$, and we want to allow our transitions to depend also on which class $C$ lies in (here it doesn't really matter whether we are counting how many times we were at a state overall, or in the current run).

Let's do the case $d=2$ first. We can think of this as defining a unary language $L$ (which we identify with a subset of $\mathbb{N}$), and allowing transitions to depend on whether $C \in L$ or not. In this case, the resulting automaton model (for some fixed $L$) remains equivalent to DFAs precisely if $L$ is regular (exercise).

The general case is similar, and left to the interested reader.

  • $\begingroup$ "you can accept every unary language" -- even undecidable ones? Well, depends what predicates you allow for "basing decisions on", I guess. $\endgroup$ – Raphael Oct 18 '16 at 11:33
  • $\begingroup$ @Raphael I potentially allow every predicate. $\endgroup$ – Yuval Filmus Oct 18 '16 at 11: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.