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
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,022
0 votes

Construct Pushdown Automaton that accepts language $x\in\{a,b\}^*, a=2b$

This is a solution for this problem I built in JFLAP
Vunag's user avatar
  • 1
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
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

Top 50 recent answers are included