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

New answers tagged

0 votes

What does DFA that accepts at least 1 a or at least 1 b mean?

It means that language accepted by the DFA contains minimum 1 'a' OR 1 'b' OR both 1 'a' and 'b'. L = {a, b, ab, ba, bb, aa, aab, baa, ....}
rahul's user avatar
  • 1
0 votes

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

You say you jump to the middle of the input. How exactly do you propose to do that with finite memory? You’ll have to remember the first n 0s, not just the number n.
gnasher729's user avatar
  • 30.4k
0 votes

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

Here, $L=\{0^n1^n\mid n\ge 0\}$ is not a regular language (it is a context-free one). Thus, $L$ cannot be recognized by a DFA (or NFA). But a Turing machine (TM), which is a more powerful FSM than ...
codeR's user avatar
  • 986
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,097
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
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
  • 986
0 votes

Algorithm to determine the regularity of a language

A subset $L ⊆ Σ^*$ is regular if and only if $q_L = \{ w \backslash L: w ∈ Σ^* \}$ is finite. The left-quotient is defined by $$ w ∈ Σ^*, L ⊆ Σ^* ↦ w \backslash L = \{ w' ∈ Σ^*: w w' ∈ L \}, $$ and ...
NinjaDarth's user avatar
0 votes

Decide if some DFA is accepted

Your answer takes care of the first part. See here for more detailed discussion on the topic "Decide whether a DFA accepts the empty language." Now for the second part, minimize the given ...
codeR's user avatar
  • 986
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
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
1 vote
Accepted

Trying to understand better the solution for $L \ regular \to L'=\left \{ xy^{R}z : xyz\in L\ , x,y,z\in\Sigma^{*} \right \} \ regular$

Note that in $\bigcup_{p,q}$ the states $p,q$ are variables, ranging over $Q$. That means we have four possibilities each. (Also $F$ in the original answer was intended to represent the set of final ...
Hendrik Jan's user avatar
  • 30.8k
3 votes
Accepted

Efficiently transforming non-recursive CFG into an NFA

Build a directed graph, with one vertex per non-terminal, and an edge $A \to B$ if there is a rule in the grammar where $A$ is on the left-hand side and $B$ appears on the right-hand side. Since you ...
D.W.'s user avatar
  • 161k
-1 votes

Finite state automata, multiple completion states?

In my opinion the answer suggested has redundant states. It can be simply made with 2 states: q0 → if $a$ → q1 (count one $a$ in this way) if $b$ → q0 (stay on initial state) q1 → if $a$,$b$ stay on ...
Asma Amir's user avatar

Top 50 recent answers are included