RACSO
R
DFA
CFG
Operations:
Reg
,
CF
PDA
Reductions:
K
,
WP
,
CFG
,
NP
,
SAT
ANTLR:
lex
,
syn
Exams
log in
,
register
,
guest
This site uses cookies only for the purpose of identifying user sessions. This is required to properly register actions.
Exercises on deterministic finite automata (DFA)
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
∈
2
N
}
\{ w \in \{a,b\}^* \mid |w|_a\in 2\mathbb{N}\}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
∈
2
N
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
∈
2
N
∧
∣
w
∣
b
∈
2
N
}
\{ w \in \{a,b\}^* \mid |w|_a\in 2\mathbb{N}\wedge |w|_b\in 2\mathbb{N} \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
∈
2
N
∧
∣
w
∣
b
∈
2
N
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
∉
2
N
∨
∣
w
∣
b
∉
2
N
}
\{ w \in \{a,b\}^* \mid |w|_a\notin 2\mathbb{N}\vee |w|_b\notin 2\mathbb{N} \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
∈
/
2
N
∨
∣
w
∣
b
∈
/
2
N
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∃
x
:
w
=
x
a
}
\{ w \in \{a,b\}^* \mid \exists x: w=xa \}
{
w
∈
{
a
,
b
}
∗
∣
∃
x
:
w
=
x
a
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∃
x
:
w
=
x
b
b
a
}
\{ w \in \{a,b\}^* \mid \exists x: w=xbba \}
{
w
∈
{
a
,
b
}
∗
∣
∃
x
:
w
=
x
bba
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∃
x
:
w
=
x
b
a
b
a
b
}
\{ w \in \{a,b\}^* \mid \exists x: w=xbabab \}
{
w
∈
{
a
,
b
}
∗
∣
∃
x
:
w
=
x
babab
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∃
x
,
y
:
(
w
=
x
a
b
y
∧
∣
y
∣
=
1
)
}
\{ w \in \{a,b\}^* \mid \exists x,y: (w=xaby \wedge |y|=1) \}
{
w
∈
{
a
,
b
}
∗
∣
∃
x
,
y
:
(
w
=
x
ab
y
∧
∣
y
∣
=
1
)}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
(
w
=
x
a
y
⇒
∣
x
∣
b
∈
2
N
)
}
\{ w \in \{a,b\}^* \mid \forall x,y: (w=xay \Rightarrow |x|_b\in 2\mathbb{N}) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
(
w
=
x
a
y
⇒
∣
x
∣
b
∈
2
N
)}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
(
w
=
x
a
y
⇒
∣
y
∣
b
∈
2
N
)
}
\{ w \in \{a,b\}^* \mid \forall x,y: (w=xay \Rightarrow |y|_b\in 2\mathbb{N}) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
(
w
=
x
a
y
⇒
∣
y
∣
b
∈
2
N
)}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
(
(
w
=
x
y
∧
∣
x
∣
≥
3
)
⇒
(
∣
x
∣
a
∈
2
N
∨
∣
x
∣
b
∈
2
N
)
)
}
\{ w \in \{a,b\}^* \mid \forall x,y: ( (w=xy \wedge |x|\geq 3) \Rightarrow (|x|_a\in 2\mathbb{N}\vee |x|_b\in 2\mathbb{N}) ) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
((
w
=
x
y
∧
∣
x
∣
≥
3
)
⇒
(
∣
x
∣
a
∈
2
N
∨
∣
x
∣
b
∈
2
N
))}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
(
(
w
=
x
y
∧
∣
x
∣
≥
3
)
⇒
(
∣
x
∣
a
∈
2
N
∨
∣
x
∣
b
∉
2
N
)
)
}
\{ w \in \{a,b\}^* \mid \forall x,y: ( (w=xy \wedge |x|\geq 3) \Rightarrow (|x|_a\in 2\mathbb{N}\vee |x|_b\notin 2\mathbb{N}) ) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
((
w
=
x
y
∧
∣
x
∣
≥
3
)
⇒
(
∣
x
∣
a
∈
2
N
∨
∣
x
∣
b
∈
/
2
N
))}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
,
z
:
(
(
w
=
x
y
z
∧
∣
y
∣
=
3
)
⇒
(
∣
y
∣
a
∈
2
N
∨
∣
y
∣
b
∉
2
N
)
)
}
\{ w \in \{a,b\}^* \mid \forall x,y,z: ( (w=xyz \wedge |y|=3) \Rightarrow (|y|_a\in 2\mathbb{N} \vee |y|_b\notin 2\mathbb{N}) ) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
,
z
:
((
w
=
x
yz
∧
∣
y
∣
=
3
)
⇒
(
∣
y
∣
a
∈
2
N
∨
∣
y
∣
b
∈
/
2
N
))}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
,
z
:
(
(
w
=
x
y
z
∧
∣
y
∣
=
3
)
⇒
(
∣
y
∣
a
∈
2
N
∨
∣
y
∣
b
∈
2
N
)
)
}
\{ w \in \{a,b\}^* \mid \forall x,y,z: ( (w=xyz \wedge |y|=3) \Rightarrow (|y|_a\in 2\mathbb{N} \vee |y|_b\in 2\mathbb{N}) ) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
,
z
:
((
w
=
x
yz
∧
∣
y
∣
=
3
)
⇒
(
∣
y
∣
a
∈
2
N
∨
∣
y
∣
b
∈
2
N
))}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
:
(
w
=
b
b
x
⇒
∣
x
∣
a
a
=
0
)
}
\{ w \in \{a,b\}^* \mid \forall x: (w=bbx \Rightarrow |x|_{aa}=0) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
:
(
w
=
bb
x
⇒
∣
x
∣
aa
=
0
)}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
b
b
b
=
0
}
\{ w \in \{a,b\}^* \mid |w|_{bbb}=0 \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
bbb
=
0
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
b
a
b
=
0
}
\{ w \in \{a,b\}^* \mid |w|_{bab}=0 \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
bab
=
0
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
b
a
=
0
∧
∣
w
∣
b
a
b
=
0
∧
∃
x
:
w
=
x
a
a
a
}
\{ w \in \{a,b\}^* \mid |w|_{aba}=0 \wedge |w|_{bab}=0 \wedge \exists x: w=xaaa \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aba
=
0
∧
∣
w
∣
bab
=
0
∧
∃
x
:
w
=
x
aaa
}
Minimum DFA for
{
w
∈
{
a
,
b
,
c
}
∗
∣
∣
w
∣
a
b
c
≤
1
}
\{ w \in \{a,b,c\}^* \mid |w|_{abc}\leq 1 \}
{
w
∈
{
a
,
b
,
c
}
∗
∣
∣
w
∣
ab
c
≤
1
}
Minimum DFA for
{
w
∈
{
a
,
b
,
c
}
∗
∣
∀
x
,
y
,
z
:
(
w
=
x
b
y
b
z
⇒
∣
y
∣
a
≥
2
)
}
\{ w \in \{a,b,c\}^* \mid \forall x,y,z: (w=xbybz \Rightarrow |y|_a\geq 2) \}
{
w
∈
{
a
,
b
,
c
}
∗
∣
∀
x
,
y
,
z
:
(
w
=
x
b
y
b
z
⇒
∣
y
∣
a
≥
2
)}
Minimum DFA for
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
2
N
}
\{ w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 2\mathbb{N} \}
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
2
N
}
Minimum DFA for
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
3
N
}
\{ w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 3\mathbb{N} \}
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
3
N
}
Minimum DFA for
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∉
3
N
}
\{ w \in \{0,1\}^* \mid \mathtt{value}_2(w)\notin 3\mathbb{N} \}
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
/
3
N
}
Minimum DFA for
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
4
N
}
\{ w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 4\mathbb{N} \}
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
4
N
}
Minimum DFA for
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∉
4
N
}
\{ w \in \{0,1\}^* \mid \mathtt{value}_2(w)\notin 4\mathbb{N} \}
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
/
4
N
}
Minimum DFA for
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
5
N
}
\{ w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 5\mathbb{N} \}
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
5
N
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
,
z
:
(
(
w
=
x
y
z
∧
∣
y
∣
=
3
)
⇒
∣
y
∣
a
=
2
)
}
\{ w \in \{a,b\}^* \mid \forall x,y,z: ((w=xyz \wedge |y|=3) \Rightarrow |y|_a=2) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
,
z
:
((
w
=
x
yz
∧
∣
y
∣
=
3
)
⇒
∣
y
∣
a
=
2
)}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
(
(
w
=
x
y
∧
∣
x
∣
∉
2
N
)
⇒
∣
x
∣
b
=
1
+
∣
x
∣
a
)
}
\{ w \in \{a,b\}^* \mid \forall x,y: ((w=xy \wedge |x|\notin 2\mathbb{N})\Rightarrow |x|_b=1+|x|_a) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
((
w
=
x
y
∧
∣
x
∣
∈
/
2
N
)
⇒
∣
x
∣
b
=
1
+
∣
x
∣
a
)}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
(
(
w
=
x
y
∧
∣
y
∣
∉
2
N
)
⇒
∣
y
∣
b
=
1
+
∣
y
∣
a
)
}
\{ w \in \{a,b\}^* \mid \forall x,y: ((w=xy \wedge |y|\notin 2\mathbb{N}) \Rightarrow |y|_b=1+|y|_a) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
x
,
y
:
((
w
=
x
y
∧
∣
y
∣
∈
/
2
N
)
⇒
∣
y
∣
b
=
1
+
∣
y
∣
a
)}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∀
y
:
(
(
∣
y
∣
=
2
∧
∣
y
∣
b
>
0
)
⇒
∣
w
∣
y
>
0
)
}
\{ w \in \{a,b\}^* \mid \forall y: ((|y|=2 \wedge |y|_b>0) \Rightarrow |w|_y>0) \}
{
w
∈
{
a
,
b
}
∗
∣
∀
y
:
((
∣
y
∣
=
2
∧
∣
y
∣
b
>
0
)
⇒
∣
w
∣
y
>
0
)}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
b
=
∣
w
∣
b
a
}
\{ w \in \{a,b\}^* \mid |w|_{ab}=|w|_{ba} \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
ab
=
∣
w
∣
ba
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
b
=
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid |w|_{ab}=|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
ab
=
∣
w
∣
b
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
b
a
=
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid |w|_{aba}=|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aba
=
∣
w
∣
b
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
b
a
+
1
=
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid |w|_{aba}+1=|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aba
+
1
=
∣
w
∣
b
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
b
a
=
∣
w
∣
a
}
\{ w \in \{a,b\}^* \mid |w|_{aba}=|w|_a \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aba
=
∣
w
∣
a
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
b
a
+
1
=
∣
w
∣
a
}
\{ w \in \{a,b\}^* \mid |w|_{aba}+1=|w|_a \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aba
+
1
=
∣
w
∣
a
}
Minimum DFA for
{
w
∈
{
a
,
b
}
∗
∣
∃
x
,
y
,
z
:
(
w
=
x
y
z
∧
∣
y
∣
b
=
3
+
∣
y
∣
a
)
}
\{ w \in \{a,b\}^* \mid \exists x,y,z: (w=xyz \wedge |y|_b=3+|y|_a) \}
{
w
∈
{
a
,
b
}
∗
∣
∃
x
,
y
,
z
:
(
w
=
x
yz
∧
∣
y
∣
b
=
3
+
∣
y
∣
a
)}
Minimum DFA for
{
x
y
∈
{
a
,
b
}
∗
∣
∣
x
∣
a
=
∣
y
∣
a
}
\{ xy \in \{a,b\}^* \mid |x|_a=|y|_a \}
{
x
y
∈
{
a
,
b
}
∗
∣
∣
x
∣
a
=
∣
y
∣
a
}
Minimum DFA for
{
x
y
∈
{
a
,
b
}
∗
∣
∣
x
∣
a
=
∣
y
∣
b
}
\{ xy \in \{a,b\}^* \mid |x|_a=|y|_b \}
{
x
y
∈
{
a
,
b
}
∗
∣
∣
x
∣
a
=
∣
y
∣
b
}
Minimum DFA for
{
x
y
∈
{
a
,
b
}
∗
∣
∣
x
∣
a
a
=
∣
y
∣
b
}
\{ xy \in \{a,b\}^* \mid |x|_{aa}=|y|_b \}
{
x
y
∈
{
a
,
b
}
∗
∣
∣
x
∣
aa
=
∣
y
∣
b
}