RACSO
DFA
CFG
Operations:
Reg
,
CF
PDA
Reductions:
K
,
WP
,
CFG
,
NP
,
SAT
ANTLR:
lexical
,
syntactic
Exams
log in
,
register
,
become guest
This site uses cookies only for the purpose of identifying user sessions. This is required to properly register actions.
Exercises on push-down automata (PDA)
Deterministic uniquely-accepting PDA for
{
a
n
b
n
∣
n
≥
0
}
\{ a^n b^n \mid n\geq 0 \}
{
a
n
b
n
∣
n
≥
0
}
Deterministic uniquely-accepting PDA for
{
a
2
n
b
n
∣
n
≥
0
}
\{ a^{2n} b^n \mid n\geq 0 \}
{
a
2
n
b
n
∣
n
≥
0
}
Deterministic uniquely-accepting PDA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
=
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid |w|_a=|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
=
∣
w
∣
b
}
Deterministic uniquely-accepting PDA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
≠
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid |w|_a\neq|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
=
∣
w
∣
b
}
Deterministic uniquely-accepting PDA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
≥
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid |w|_a\geq|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
≥
∣
w
∣
b
}
Deterministic uniquely-accepting PDA for
{
w
∈
{
a
,
b
}
∗
∣
2
∣
w
∣
a
=
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid 2|w|_a=|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
2∣
w
∣
a
=
∣
w
∣
b
}
Deterministic uniquely-accepting PDA for
{
w
∈
{
a
,
b
}
∗
∣
2
∣
w
∣
a
≥
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid 2|w|_a\geq|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
2∣
w
∣
a
≥
∣
w
∣
b
}
Deterministic uniquely-accepting PDA for
{
w
∈
{
a
,
b
}
∗
∣
2
∣
w
∣
a
≤
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid 2|w|_a\leq|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
2∣
w
∣
a
≤
∣
w
∣
b
}
Uniquely-accepting PDA for
{
a
i
b
j
∣
j
≤
i
≤
2
j
}
\{ a^i b^j \mid j\leq i\leq 2j \}
{
a
i
b
j
∣
j
≤
i
≤
2
j
}
Deterministic uniquely-accepting PDA for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
a
=
∣
w
∣
b
}
\{ w \in \{a,b\}^* \mid |w|_{aa}=|w|_b \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aa
=
∣
w
∣
b
}
Deterministic uniquely-accepting PDA for
{
a
i
b
j
c
k
∣
i
=
j
+
k
}
\{ a^i b^j c^k \mid i=j+k \}
{
a
i
b
j
c
k
∣
i
=
j
+
k
}
Deterministic uniquely-accepting PDA for
{
a
i
b
j
c
k
∣
j
=
i
+
k
}
\{ a^i b^j c^k \mid j=i+k \}
{
a
i
b
j
c
k
∣
j
=
i
+
k
}
PDA for
{
a
i
b
j
c
k
∣
i
=
j
∨
i
=
k
}
\{ a^i b^j c^k \mid i=j \vee i=k \}
{
a
i
b
j
c
k
∣
i
=
j
∨
i
=
k
}
PDA for
{
a
i
b
j
c
k
∣
i
=
j
∨
j
=
k
}
\{ a^i b^j c^k \mid i=j \vee j=k \}
{
a
i
b
j
c
k
∣
i
=
j
∨
j
=
k
}
Uniquely-accepting PDA for
{
a
i
b
j
c
k
d
∣
i
=
j
}
∪
{
a
i
b
j
c
k
e
∣
j
=
k
}
\{ a^i b^j c^k d \mid i=j \} \cup \{a^i b^j c^k e\mid j=k \}
{
a
i
b
j
c
k
d
∣
i
=
j
}
∪
{
a
i
b
j
c
k
e
∣
j
=
k
}
Uniquely-accepting PDA for
{
w
∈
{
a
,
b
}
∗
∣
w
=
w
R
}
\{ w \in \{a,b\}^* \mid w=w^R \}
{
w
∈
{
a
,
b
}
∗
∣
w
=
w
R
}
Deterministic uniquely-accepting PDA for the well-parenthesized words over
{
(
,
)
}
\{ ( , ) \}
{(
,
)}
Deterministic uniquely-accepting PDA for the well-parenthesized words over
{
[
,
]
,
(
,
)
}
\{ [ , ] , ( , ) \}
{[
,
]
,
(
,
)}
Deterministic uniquely-accepting PDA for
{
x
c
y
∣
x
,
y
∈
{
a
,
b
}
∗
∧
∣
x
∣
a
=
∣
y
∣
b
}
\{ xcy \mid x,y\in\{a,b\}^* \wedge |x|_{a}=|y|_{b} \}
{
x
cy
∣
x
,
y
∈
{
a
,
b
}
∗
∧
∣
x
∣
a
=
∣
y
∣
b
}
Deterministic uniquely-accepting PDA for
{
x
c
y
∣
x
,
y
∈
{
a
,
b
}
∗
∧
∣
x
∣
a
b
=
∣
y
∣
b
a
}
\{ xcy \mid x,y\in\{a,b\}^* \wedge |x|_{ab}=|y|_{ba} \}
{
x
cy
∣
x
,
y
∈
{
a
,
b
}
∗
∧
∣
x
∣
ab
=
∣
y
∣
ba
}
Deterministic uniquely-accepting PDA for
{
x
c
y
∣
x
,
y
∈
{
a
,
b
}
∗
∧
∣
x
∣
a
b
a
=
∣
y
∣
b
a
b
}
\{ xcy \mid x,y\in\{a,b\}^* \wedge |x|_{aba}=|y|_{bab} \}
{
x
cy
∣
x
,
y
∈
{
a
,
b
}
∗
∧
∣
x
∣
aba
=
∣
y
∣
bab
}