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 context-free operations
Context-free description for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
=
∣
w
∣
b
∧
∣
w
∣
a
b
b
a
>
0
}
\{ w \in \{a,b\}^* \mid |w|_a=|w|_b\;\wedge\;|w|_{abba}>0 \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
=
∣
w
∣
b
∧
∣
w
∣
abba
>
0
}
Context-free description for
{
w
∈
{
0
,
1
}
∗
∣
w
=
w
R
∧
v
a
l
u
e
2
(
w
)
∈
5
N
}
\{ w \in \{0,1\}^* \mid w=w^R\;\wedge\;\mathtt{value}_2(w)\in 5\mathbb{N} \}
{
w
∈
{
0
,
1
}
∗
∣
w
=
w
R
∧
value
2
(
w
)
∈
5
N
}
Context-free description for the well-parenthesized words over
{
(
,
)
}
\{ ( , ) \}
{(
,
)}
with no occurrence of
(
(
(
(((
(((
Context-free description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
)
∣
w
1
,
w
2
∈
{
a
,
b
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
∧
w
1
=
w
1
R
∧
∣
w
2
∣
a
a
=
0
}
\{ \mathtt{intercal}(w_1,w_2) \mid w_1,w_2\in\{a,b\}^*\;\wedge\;|w_1|=|w_2|\;\wedge\;w_1=w_1^R\;\wedge\;|w_2|_{aa}=0 \}
{
intercal
(
w
1
,
w
2
)
∣
w
1
,
w
2
∈
{
a
,
b
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
∧
w
1
=
w
1
R
∧
∣
w
2
∣
aa
=
0
}
,
where
i
n
t
e
r
c
a
l
(
a
1
w
1
,
…
,
a
n
w
n
)
=
a
1
…
a
n
i
n
t
e
r
c
a
l
(
w
1
,
…
,
w
n
)
\mathtt{intercal}(a_1w_1,\ldots,a_nw_n)=a_1\ldots a_n\mathtt{intercal}(w_1,\ldots,w_n)
intercal
(
a
1
w
1
,
…
,
a
n
w
n
)
=
a
1
…
a
n
intercal
(
w
1
,
…
,
w
n
)
and
i
n
t
e
r
c
a
l
(
λ
,
…
,
λ
)
=
λ
\mathtt{intercal}(\lambda,\ldots,\lambda)=\lambda
intercal
(
λ
,
…
,
λ
)
=
λ
Context-free description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
)
∣
w
1
,
w
2
∈
{
a
,
b
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
∧
∣
w
2
∣
a
a
=
0
∧
∀
x
1
,
y
1
,
x
2
,
y
2
:
(
w
1
=
x
1
y
1
∧
w
2
=
x
2
y
2
∧
∣
x
1
∣
=
∣
x
2
∣
⇒
∣
x
1
∣
a
≥
∣
x
2
∣
a
)
}
\{ \mathtt{intercal}(w_1,w_2) \mid w_1,w_2\in\{a,b\}^*\;\wedge\;|w_1|=|w_2|\;\wedge\;|w_2|_{aa}=0\;\wedge\;\forall x_1,y_1,x_2,y_2:(w_1=x_1y_1\;\wedge\;w_2=x_2y_2\;\wedge\;|x_1|=|x_2|\;\Rightarrow\;|x_1|_a\geq|x_2|_a) \}
{
intercal
(
w
1
,
w
2
)
∣
w
1
,
w
2
∈
{
a
,
b
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
∧
∣
w
2
∣
aa
=
0
∧
∀
x
1
,
y
1
,
x
2
,
y
2
:
(
w
1
=
x
1
y
1
∧
w
2
=
x
2
y
2
∧
∣
x
1
∣
=
∣
x
2
∣
⇒
∣
x
1
∣
a
≥
∣
x
2
∣
a
)}
,
where
i
n
t
e
r
c
a
l
(
a
1
w
1
,
…
,
a
n
w
n
)
=
a
1
…
a
n
i
n
t
e
r
c
a
l
(
w
1
,
…
,
w
n
)
\mathtt{intercal}(a_1w_1,\ldots,a_nw_n)=a_1\ldots a_n\mathtt{intercal}(w_1,\ldots,w_n)
intercal
(
a
1
w
1
,
…
,
a
n
w
n
)
=
a
1
…
a
n
intercal
(
w
1
,
…
,
w
n
)
and
i
n
t
e
r
c
a
l
(
λ
,
…
,
λ
)
=
λ
\mathtt{intercal}(\lambda,\ldots,\lambda)=\lambda
intercal
(
λ
,
…
,
λ
)
=
λ
Context-free description for
{
a
i
b
j
a
k
b
r
a
s
b
t
∣
i
+
k
+
s
=
j
+
r
+
t
}
\{ a^ib^ja^kb^ra^sb^t \mid i+k+s=j+r+t \}
{
a
i
b
j
a
k
b
r
a
s
b
t
∣
i
+
k
+
s
=
j
+
r
+
t
}
Context-free description for
{
a
i
b
j
a
k
b
r
a
s
b
t
∣
i
+
k
+
s
=
2
(
j
+
r
+
t
)
}
\{ a^ib^ja^kb^ra^sb^t \mid i+k+s=2(j+r+t) \}
{
a
i
b
j
a
k
b
r
a
s
b
t
∣
i
+
k
+
s
=
2
(
j
+
r
+
t
)}
Context-free description for
{
a
i
b
j
a
k
b
r
a
s
b
t
∣
i
+
k
+
r
+
t
=
j
+
s
}
\{ a^ib^ja^kb^ra^sb^t \mid i+k+r+t=j+s \}
{
a
i
b
j
a
k
b
r
a
s
b
t
∣
i
+
k
+
r
+
t
=
j
+
s
}
Context-free description for
{
w
1
a
w
2
a
w
3
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
0
+
∣
w
3
∣
1
∧
∣
w
1
w
2
∣
111
≥
1
}
\{ w_1aw_2aw_3 \mid w_1,w_2,w_3\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|_0+|w_3|_1\;\wedge\;|w_1w_2|_{111}\geq 1 \}
{
w
1
a
w
2
a
w
3
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
0
+
∣
w
3
∣
1
∧
∣
w
1
w
2
∣
111
≥
1
}
Context-free description for
{
a
n
b
w
1
a
w
2
∣
w
1
,
w
2
∈
{
a
,
b
}
∗
∧
n
=
∣
w
2
∣
∧
∣
w
1
w
2
∣
a
a
a
=
0
∧
w
1
=
w
1
R
}
\{ a^nbw_1aw_2 \mid w_1,w_2\in\{a,b\}^*\;\wedge\;n=|w_2|\;\wedge\;|w_1w_2|_{aaa}=0\;\wedge\;w_1=w_1^R \}
{
a
n
b
w
1
a
w
2
∣
w
1
,
w
2
∈
{
a
,
b
}
∗
∧
n
=
∣
w
2
∣
∧
∣
w
1
w
2
∣
aaa
=
0
∧
w
1
=
w
1
R
}
Context-free description for
{
w
1
a
w
2
a
w
3
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
3
∣
∧
v
a
l
u
e
2
(
w
1
w
3
)
∈
12
N
∧
w
2
∈
{
0
n
1
n
∣
n
≥
0
}
}
\{ w_1aw_2aw_3 \mid w_1,w_2,w_3\in\{0,1\}^*\;\wedge\;|w_1|=|w_3|\;\wedge\;\mathtt{value}_2(w_1w_3)\in 12\mathbb{N}\;\wedge\;w_2\in\{0^n1^n\mid n\geq 0\} \}
{
w
1
a
w
2
a
w
3
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
3
∣
∧
value
2
(
w
1
w
3
)
∈
12
N
∧
w
2
∈
{
0
n
1
n
∣
n
≥
0
}}