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 regular operations
Regular description for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
a
a
>
0
∨
∣
w
∣
b
b
b
>
0
∨
∣
w
∣
a
b
a
>
0
∨
∣
w
∣
b
a
b
>
0
}
\{ w \in \{a,b\}^* \mid |w|_{aaa}>0\;\vee\;|w|_{bbb}>0\;\vee\;|w|_{aba}>0\;\vee\;|w|_{bab}>0 \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aaa
>
0
∨
∣
w
∣
bbb
>
0
∨
∣
w
∣
aba
>
0
∨
∣
w
∣
bab
>
0
}
Regular description for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
a
a
>
0
∧
∣
w
∣
b
b
b
>
0
∧
∣
w
∣
a
b
a
>
0
∧
∣
w
∣
b
a
b
>
0
}
\{ w \in \{a,b\}^* \mid |w|_{aaa}>0\;\wedge\;|w|_{bbb}>0\;\wedge\;|w|_{aba}>0\;\wedge\;|w|_{bab}>0 \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aaa
>
0
∧
∣
w
∣
bbb
>
0
∧
∣
w
∣
aba
>
0
∧
∣
w
∣
bab
>
0
}
Regular description for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
a
a
=
∣
w
∣
b
b
b
=
1
}
\{ w \in \{a,b\}^* \mid |w|_{aaa}=|w|_{bbb}=1 \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aaa
=
∣
w
∣
bbb
=
1
}
Regular description for
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
b
a
=
∣
w
∣
b
a
b
=
1
}
\{ w \in \{a,b\}^* \mid |w|_{aba}=|w|_{bab}=1 \}
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
aba
=
∣
w
∣
bab
=
1
}
Regular description for
{
w
∈
{
a
,
b
}
∗
∣
∃
w
1
,
w
2
:
(
w
=
w
1
a
w
2
∧
∣
w
2
∣
=
5
)
∧
∣
w
∣
b
b
b
>
0
}
\{ w \in \{a,b\}^* \mid \exists w_1,w_2: (w=w_1aw_2\;\wedge\;|w_2|=5)\;\wedge\;|w|_{bbb}>0 \}
{
w
∈
{
a
,
b
}
∗
∣
∃
w
1
,
w
2
:
(
w
=
w
1
a
w
2
∧
∣
w
2
∣
=
5
)
∧
∣
w
∣
bbb
>
0
}
Regular description for
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
12
˙
}
\{ w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in\dot{12}\}
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
12
˙
}
Regular description for
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
20
˙
}
\{ w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in\dot{20}\}
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
20
˙
}
Regular description for
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
60
˙
}
\{ w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in\dot{60}\}
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
60
˙
}
Regular description for
σ
(
L
)
\sigma(L)
σ
(
L
)
where
L
=
{
w
∈
{
a
,
b
}
∗
∣
∃
x
,
y
:
(
w
=
x
a
y
∧
∣
y
∣
=
2
)
}
L=\{ w \in \{a,b\}^* \mid \exists x,y: (w=xay\;\wedge\;|y|=2) \}
L
=
{
w
∈
{
a
,
b
}
∗
∣
∃
x
,
y
:
(
w
=
x
a
y
∧
∣
y
∣
=
2
)}
and
σ
\sigma
σ
is the morphism defined by
σ
(
a
)
=
a
b
a
\sigma(a)=aba
σ
(
a
)
=
aba
and
σ
(
b
)
=
b
a
b
\sigma(b)=bab
σ
(
b
)
=
bab
Regular description for
σ
(
L
)
\sigma(L)
σ
(
L
)
where
L
=
{
w
∈
{
a
,
b
,
c
}
∗
∣
∃
x
,
y
:
(
(
w
=
x
a
y
∨
w
=
x
c
y
)
∧
∣
y
∣
=
1
)
}
L=\{ w \in \{a,b,c\}^* \mid \exists x,y: ((w=xay\;\vee\;w=xcy)\;\wedge\;|y|=1) \}
L
=
{
w
∈
{
a
,
b
,
c
}
∗
∣
∃
x
,
y
:
((
w
=
x
a
y
∨
w
=
x
cy
)
∧
∣
y
∣
=
1
)}
and
σ
\sigma
σ
is the morphism defined by
σ
(
a
)
=
a
b
a
\sigma(a)=aba
σ
(
a
)
=
aba
,
σ
(
b
)
=
a
a
\sigma(b)=aa
σ
(
b
)
=
aa
and
σ
(
c
)
=
b
\sigma(c)=b
σ
(
c
)
=
b
Regular description for
σ
(
L
)
\sigma(L)
σ
(
L
)
where
L
=
{
w
∈
{
a
,
b
}
∗
∣
∃
x
,
y
:
(
w
=
x
a
y
∧
∣
y
∣
=
2
)
}
L=\{ w \in \{a,b\}^* \mid \exists x,y: (w=xay\;\wedge\;|y|=2) \}
L
=
{
w
∈
{
a
,
b
}
∗
∣
∃
x
,
y
:
(
w
=
x
a
y
∧
∣
y
∣
=
2
)}
and
σ
\sigma
σ
is the substitution defined by
σ
(
a
)
=
{
a
a
}
∗
\sigma(a)=\{aa\}^*
σ
(
a
)
=
{
aa
}
∗
and
σ
(
b
)
=
{
a
,
a
b
a
,
b
a
b
}
\sigma(b)=\{a,aba,bab\}
σ
(
b
)
=
{
a
,
aba
,
bab
}
Regular description for the language recognized by the NFA with set of states
{
0
,
1
,
2
,
3
,
4
,
5
}
\{0,1,2,3,4,5\}
{
0
,
1
,
2
,
3
,
4
,
5
}
,
initial state
0
0
0
, accepting state
4
4
4
, and transitions
δ
(
0
,
a
)
=
{
1
,
3
}
,
δ
(
0
,
b
)
=
4
,
δ
(
1
,
a
)
=
4
,
δ
(
1
,
b
)
=
{
2
,
3
}
,
δ
(
2
,
b
)
=
5
,
δ
(
3
,
a
)
=
2
,
δ
(
4
,
a
)
=
{
0
,
5
}
,
δ
(
4
,
b
)
=
{
0
,
2
}
,
δ
(
5
,
a
)
=
4
\delta(0,a)=\{1,3\},\;\delta(0,b)=4,\;\delta(1,a)=4,\;\delta(1,b)=\{2,3\},\;\delta(2,b)=5,\;\delta(3,a)=2,\;\delta(4,a)=\{0,5\},\;\delta(4,b)=\{0,2\},\;\delta(5,a)=4
δ
(
0
,
a
)
=
{
1
,
3
}
,
δ
(
0
,
b
)
=
4
,
δ
(
1
,
a
)
=
4
,
δ
(
1
,
b
)
=
{
2
,
3
}
,
δ
(
2
,
b
)
=
5
,
δ
(
3
,
a
)
=
2
,
δ
(
4
,
a
)
=
{
0
,
5
}
,
δ
(
4
,
b
)
=
{
0
,
2
}
,
δ
(
5
,
a
)
=
4
Regular description for the language recognized by the NFA with set of states
{
0
,
1
,
2
,
3
,
4
,
5
}
\{0,1,2,3,4,5\}
{
0
,
1
,
2
,
3
,
4
,
5
}
,
initial states
{
2
,
5
}
\{2,5\}
{
2
,
5
}
, accepting state
4
4
4
, and transitions
δ
(
0
,
a
)
=
{
1
,
3
}
,
δ
(
0
,
b
)
=
4
,
δ
(
1
,
a
)
=
4
,
δ
(
1
,
b
)
=
{
2
,
3
}
,
δ
(
2
,
b
)
=
5
,
δ
(
3
,
a
)
=
2
,
δ
(
4
,
a
)
=
{
0
,
5
}
,
δ
(
4
,
b
)
=
{
0
,
2
}
,
δ
(
5
,
a
)
=
4
\delta(0,a)=\{1,3\},\;\delta(0,b)=4,\;\delta(1,a)=4,\;\delta(1,b)=\{2,3\},\;\delta(2,b)=5,\;\delta(3,a)=2,\;\delta(4,a)=\{0,5\},\;\delta(4,b)=\{0,2\},\;\delta(5,a)=4
δ
(
0
,
a
)
=
{
1
,
3
}
,
δ
(
0
,
b
)
=
4
,
δ
(
1
,
a
)
=
4
,
δ
(
1
,
b
)
=
{
2
,
3
}
,
δ
(
2
,
b
)
=
5
,
δ
(
3
,
a
)
=
2
,
δ
(
4
,
a
)
=
{
0
,
5
}
,
δ
(
4
,
b
)
=
{
0
,
2
}
,
δ
(
5
,
a
)
=
4
Regular description for
{
a
n
∣
n
∈
D
}
\{a^n\mid n\in D\}
{
a
n
∣
n
∈
D
}
, where
D
D
D
is the set of distances of paths (with allowed repetition of nodes in the path)
from node
0
0
0
to node
4
4
4
in the directed graph with edges labelled with lengths whose set of nodes is
{
0
,
1
,
2
,
3
,
4
}
\{0,1,2,3,4\}
{
0
,
1
,
2
,
3
,
4
}
and whose set of edges is
{
0
→
4
1
,
1
→
4
2
,
1
→
6
3
,
2
→
4
0
,
2
→
2
4
,
3
→
2
0
,
4
→
4
3
}
\{0\xrightarrow{4}1,\;1\xrightarrow{4}2,\;1\xrightarrow{6}3,\;2\xrightarrow{4}0,\;2\xrightarrow{2}4,\;3\xrightarrow{2}0,\;4\xrightarrow{4}3\}
{
0
4
1
,
1
4
2
,
1
6
3
,
2
4
0
,
2
2
4
,
3
2
0
,
4
4
3
}
Regular description for
{
a
n
∣
n
∈
D
}
\{a^n\mid n\in D\}
{
a
n
∣
n
∈
D
}
, where
D
D
D
is the set of distances of paths (with allowed repetition of nodes in the path)
from node
0
0
0
to node
5
5
5
in the directed graph with edges labelled with lengths whose set of nodes is
{
0
,
1
,
2
,
3
,
4
,
5
}
\{0,1,2,3,4,5\}
{
0
,
1
,
2
,
3
,
4
,
5
}
and whose set of edges is
{
0
→
7
1
,
0
→
4
2
,
1
→
7
1
,
1
→
9
3
,
2
→
4
4
,
2
→
3
5
,
3
→
4
0
,
4
→
5
2
,
4
→
3
3
,
5
→
9
4
}
\{0\xrightarrow{7}1,\;0\xrightarrow{4}2,\;1\xrightarrow{7}1,\;1\xrightarrow{9}3,\;2\xrightarrow{4}4,\;2\xrightarrow{3}5,\;3\xrightarrow{4}0,\;4\xrightarrow{5}2,\;4\xrightarrow{3}3,\;5\xrightarrow{9}4\}
{
0
7
1
,
0
4
2
,
1
7
1
,
1
9
3
,
2
4
4
,
2
3
5
,
3
4
0
,
4
5
2
,
4
3
3
,
5
9
4
}
Regular description for
σ
(
L
)
\sigma(L)
σ
(
L
)
where
L
=
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
∈
2
˙
}
L=\{ w \in \{a,b\}^* \mid |w|_a\in\dot{2} \}
L
=
{
w
∈
{
a
,
b
}
∗
∣
∣
w
∣
a
∈
2
˙
}
and
σ
\sigma
σ
is the transducer with states
{
0
,
1
,
2
}
\{0,1,2\}
{
0
,
1
,
2
}
, initial state
0
0
0
, and transitions
0
→
a
∣
a
b
a
1
,
0
→
b
∣
b
b
2
,
1
→
a
∣
b
2
,
1
→
b
∣
a
0
,
2
→
a
∣
a
1
,
2
→
b
∣
b
b
b
a
0
0\xrightarrow{a\,|\,aba}1,\;0\xrightarrow{b\,|\,bb}2,\;1\xrightarrow{a\,|\,b}2,\;1\xrightarrow{b\,|\,a}0,\;2\xrightarrow{a\,|\,a}1,\;2\xrightarrow{b\,|\,bbba}0
0
a
∣
aba
1
,
0
b
∣
bb
2
,
1
a
∣
b
2
,
1
b
∣
a
0
,
2
a
∣
a
1
,
2
b
∣
bbba
0
Regular description for
σ
(
L
)
\sigma(L)
σ
(
L
)
where
L
=
{
x
a
y
∈
{
a
,
b
}
∗
∣
∣
y
∣
=
1
}
L=\{ xay \in \{a,b\}^* \mid |y|=1 \}
L
=
{
x
a
y
∈
{
a
,
b
}
∗
∣
∣
y
∣
=
1
}
and
σ
\sigma
σ
is the transducer with states
{
0
,
1
}
\{0,1\}
{
0
,
1
}
, initial state
0
0
0
, and transitions
0
→
a
∣
a
b
a
0
,
0
→
b
∣
b
1
,
1
→
a
∣
b
0
,
1
→
b
∣
a
a
1
0\xrightarrow{a\,|\,aba}0,\;0\xrightarrow{b\,|\,b}1,\;1\xrightarrow{a\,|\,b}0,\;1\xrightarrow{b\,|\,aa}1
0
a
∣
aba
0
,
0
b
∣
b
1
,
1
a
∣
b
0
,
1
b
∣
aa
1
Regular description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
)
∣
w
1
,
w
2
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
∧
v
a
l
u
e
2
(
w
1
)
>
v
a
l
u
e
2
(
w
2
)
}
\{ \mathtt{intercal}(w_1,w_2) \mid w_1,w_2\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|\;\wedge\;\mathtt{value}_2(w_1)>\mathtt{value}_2(w_2) \}
{
intercal
(
w
1
,
w
2
)
∣
w
1
,
w
2
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
∧
value
2
(
w
1
)
>
value
2
(
w
2
)}
,
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
(
λ
,
…
,
λ
)
=
λ
Regular description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
)
∣
w
1
,
w
2
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
∧
v
a
l
u
e
2
(
w
1
)
<
v
a
l
u
e
2
(
w
2
)
}
\{ \mathtt{intercal}(w_1,w_2) \mid w_1,w_2\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|\;\wedge\;\mathtt{value}_2(w_1)<\mathtt{value}_2(w_2) \}
{
intercal
(
w
1
,
w
2
)
∣
w
1
,
w
2
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
∧
value
2
(
w
1
)
<
value
2
(
w
2
)}
,
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
(
λ
,
…
,
λ
)
=
λ
Regular description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
,
w
3
)
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
∧
v
a
l
u
e
2
(
w
1
)
>
v
a
l
u
e
2
(
w
2
)
>
v
a
l
u
e
2
(
w
3
)
}
\{ \mathtt{intercal}(w_1,w_2,w_3) \mid w_1,w_2,w_3\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|=|w_3|\;\wedge\;\mathtt{value}_2(w_1)>\mathtt{value}_2(w_2)>\mathtt{value}_2(w_3) \}
{
intercal
(
w
1
,
w
2
,
w
3
)
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
∧
value
2
(
w
1
)
>
value
2
(
w
2
)
>
value
2
(
w
3
)}
,
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
(
λ
,
…
,
λ
)
=
λ
Regular description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
,
w
3
)
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
∧
v
a
l
u
e
2
(
w
1
)
>
v
a
l
u
e
2
(
w
2
)
<
v
a
l
u
e
2
(
w
3
)
}
\{ \mathtt{intercal}(w_1,w_2,w_3) \mid w_1,w_2,w_3\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|=|w_3|\;\wedge\;\mathtt{value}_2(w_1)>\mathtt{value}_2(w_2)<\mathtt{value}_2(w_3) \}
{
intercal
(
w
1
,
w
2
,
w
3
)
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
∧
value
2
(
w
1
)
>
value
2
(
w
2
)
<
value
2
(
w
3
)}
,
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
(
λ
,
…
,
λ
)
=
λ
Regular description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
3
)
∣
∃
w
2
:
(
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
∧
v
a
l
u
e
2
(
w
1
)
>
v
a
l
u
e
2
(
w
2
)
>
v
a
l
u
e
2
(
w
3
)
)
}
\{ \mathtt{intercal}(w_1,w_3) \mid \exists w_2: (w_1,w_2,w_3\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|=|w_3|\;\wedge\;\mathtt{value}_2(w_1)>\mathtt{value}_2(w_2)>\mathtt{value}_2(w_3)) \}
{
intercal
(
w
1
,
w
3
)
∣
∃
w
2
:
(
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
∧
value
2
(
w
1
)
>
value
2
(
w
2
)
>
value
2
(
w
3
))}
,
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
(
λ
,
…
,
λ
)
=
λ
Regular description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
,
w
3
)
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
∧
v
a
l
u
e
2
(
w
1
)
+
v
a
l
u
e
2
(
w
2
)
=
v
a
l
u
e
2
(
w
3
)
}
\{ \mathtt{intercal}(w_1,w_2,w_3) \mid w_1,w_2,w_3\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|=|w_3|\;\wedge\;\mathtt{value}_2(w_1)+\mathtt{value}_2(w_2)=\mathtt{value}_2(w_3) \}
{
intercal
(
w
1
,
w
2
,
w
3
)
∣
w
1
,
w
2
,
w
3
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
∧
value
2
(
w
1
)
+
value
2
(
w
2
)
=
value
2
(
w
3
)}
,
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
(
λ
,
…
,
λ
)
=
λ
Regular description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
,
w
3
,
w
4
)
∣
w
1
,
w
2
,
w
3
,
w
4
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
=
∣
w
4
∣
∧
v
a
l
u
e
2
(
w
1
)
+
v
a
l
u
e
2
(
w
2
)
=
v
a
l
u
e
2
(
w
3
)
>
v
a
l
u
e
2
(
w
4
)
}
\{ \mathtt{intercal}(w_1,w_2,w_3,w_4) \mid w_1,w_2,w_3,w_4\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|=|w_3|=|w_4|\;\wedge\;\mathtt{value}_2(w_1)+\mathtt{value}_2(w_2)=\mathtt{value}_2(w_3)>\mathtt{value}_2(w_4) \}
{
intercal
(
w
1
,
w
2
,
w
3
,
w
4
)
∣
w
1
,
w
2
,
w
3
,
w
4
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
=
∣
w
4
∣
∧
value
2
(
w
1
)
+
value
2
(
w
2
)
=
value
2
(
w
3
)
>
value
2
(
w
4
)}
,
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
(
λ
,
…
,
λ
)
=
λ
Regular description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
,
w
4
)
∣
∃
w
3
:
(
w
1
,
w
2
,
w
3
,
w
4
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
=
∣
w
4
∣
∧
v
a
l
u
e
2
(
w
1
)
+
v
a
l
u
e
2
(
w
2
)
=
v
a
l
u
e
2
(
w
3
)
>
v
a
l
u
e
2
(
w
4
)
)
}
\{ \mathtt{intercal}(w_1,w_2,w_4) \mid \exists w_3: (w_1,w_2,w_3,w_4\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|=|w_3|=|w_4|\;\wedge\;\mathtt{value}_2(w_1)+\mathtt{value}_2(w_2)=\mathtt{value}_2(w_3)>\mathtt{value}_2(w_4)) \}
{
intercal
(
w
1
,
w
2
,
w
4
)
∣
∃
w
3
:
(
w
1
,
w
2
,
w
3
,
w
4
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
=
∣
w
4
∣
∧
value
2
(
w
1
)
+
value
2
(
w
2
)
=
value
2
(
w
3
)
>
value
2
(
w
4
))}
,
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
(
λ
,
…
,
λ
)
=
λ
Regular description for
{
i
n
t
e
r
c
a
l
(
w
1
,
w
2
,
w
4
,
w
5
)
∣
∃
w
3
:
(
w
1
,
w
2
,
w
3
,
w
4
,
w
5
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
=
∣
w
4
∣
=
∣
w
5
∣
∧
v
a
l
u
e
2
(
w
1
)
+
v
a
l
u
e
2
(
w
2
)
=
v
a
l
u
e
2
(
w
3
)
>
v
a
l
u
e
2
(
w
4
)
+
v
a
l
u
e
2
(
w
5
)
)
}
\{ \mathtt{intercal}(w_1,w_2,w_4,w_5) \mid \exists w_3: (w_1,w_2,w_3,w_4,w_5\in\{0,1\}^*\;\wedge\;|w_1|=|w_2|=|w_3|=|w_4|=|w_5|\;\wedge\;\mathtt{value}_2(w_1)+\mathtt{value}_2(w_2)=\mathtt{value}_2(w_3)>\mathtt{value}_2(w_4)+\mathtt{value}_2(w_5)) \}
{
intercal
(
w
1
,
w
2
,
w
4
,
w
5
)
∣
∃
w
3
:
(
w
1
,
w
2
,
w
3
,
w
4
,
w
5
∈
{
0
,
1
}
∗
∧
∣
w
1
∣
=
∣
w
2
∣
=
∣
w
3
∣
=
∣
w
4
∣
=
∣
w
5
∣
∧
value
2
(
w
1
)
+
value
2
(
w
2
)
=
value
2
(
w
3
)
>
value
2
(
w
4
)
+
value
2
(
w
5
))}
,
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
(
λ
,
…
,
λ
)
=
λ