Skip to main content
Share Your Experience: Take the 2024 Developer Survey
3 votes

Do multi-acceptance/multi-language automata exist in literature?

There have been studies on something called colored finite automata, which seem very close to your definition. Other colored models, e.g. regular expressions, also exist. I haven't work on this ...
sgorblex's user avatar
2 votes
Accepted

Proof that the mind/brain is not a finite state machine by recognizing an unrecognizable language?

Recognizing a language means recognizing all cases correctly, not just the few specific cases you have in mind when you say it's obvious that a human can recognize the language. The reason a finite ...
benrg's user avatar
  • 2,157
1 vote

Proof that the mind/brain is not a finite state machine by recognizing an unrecognizable language?

I think whether you believe that a human can recognise a non-regular language like $L = \{0^n1^n : n \geq 0\}$ depends somewhat on your philosophical convictions. Indeed, it is easy to design a ...
Knogger's user avatar
  • 1,107
1 vote
Accepted

Is $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$ regular

Yes, you are correct. Given $\sigma_1, \sigma_2, \sigma_3 \in \Sigma$ and $u, v \in \Sigma^*$, $L_2$ can be expressed as $0(0+1)^{2n+1}0 + 1(0+1)^{2n+1}1$, which is of course regular. On the other ...
codeR's user avatar
  • 1,057
1 vote

The equational theory of regular languages has no finite set of axioms for general alphabets

The axioms $$ (a b) c = a (b c),\quad a 1 = a = 1 a,\quad a 0 b = 0,\quad a (b + c) d = a b d + a c d,\\ (a + b) + c = a + (b + c),\quad a + 0 = a = 0 + a,\quad a + b = b + a,\quad a + a = a,\\ a^* ≥ ...
NinjaDarth's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible