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 reductions of CFG
{
⟨
g
1
,
g
2
⟩
∈
C
F
G
(
{
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
≠
∅
}
≤
{
⟨
G
1
,
G
2
,
G
3
⟩
∣
L
(
G
1
)
∩
L
(
G
2
)
≠
∅
∧
L
(
G
1
)
∩
L
(
G
3
)
≠
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
≠
∅
}
\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)\neq\emptyset\}\quad\leq\quad\{\langle G_1,G_2,G_3\rangle\mid\mathcal{L}(G_1)\cap\mathcal{L}(G_2)\neq\emptyset\;\wedge\;\mathcal{L}(G_1)\cap\mathcal{L}(G_3)\neq\emptyset\;\wedge\;\mathcal{L}(G_2)\cap\mathcal{L}(G_3)\neq\emptyset\}
{⟨
g
1
,
g
2
⟩
∈
CFG
({
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
=
∅
}
≤
{⟨
G
1
,
G
2
,
G
3
⟩
∣
L
(
G
1
)
∩
L
(
G
2
)
=
∅
∧
L
(
G
1
)
∩
L
(
G
3
)
=
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
=
∅
}
{
⟨
g
1
,
g
2
⟩
∈
C
F
G
(
{
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
≠
∅
}
≤
{
⟨
G
1
,
G
2
,
G
3
⟩
∣
L
(
G
1
)
∩
L
(
G
2
)
≠
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
≠
∅
∧
L
(
G
1
)
∩
L
(
G
3
)
=
∅
}
\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)\neq\emptyset\}\quad\leq\quad\{\langle G_1,G_2,G_3\rangle\mid\mathcal{L}(G_1)\cap\mathcal{L}(G_2)\neq\emptyset\;\wedge\;\mathcal{L}(G_2)\cap\mathcal{L}(G_3)\neq\emptyset\;\wedge\;\mathcal{L}(G_1)\cap\mathcal{L}(G_3)=\emptyset\}
{⟨
g
1
,
g
2
⟩
∈
CFG
({
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
=
∅
}
≤
{⟨
G
1
,
G
2
,
G
3
⟩
∣
L
(
G
1
)
∩
L
(
G
2
)
=
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
=
∅
∧
L
(
G
1
)
∩
L
(
G
3
)
=
∅
}
{
⟨
g
1
,
g
2
⟩
∈
C
F
G
(
{
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
≠
∅
}
≤
{
⟨
G
1
,
G
2
,
G
3
⟩
∈
C
F
G
(
{
a
,
b
}
)
3
∣
L
(
G
1
)
∩
L
(
G
2
)
≠
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
≠
∅
∧
L
(
G
1
)
∩
L
(
G
3
)
=
∅
}
\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)\neq\emptyset\}\quad\leq\quad\{\langle G_1,G_2,G_3\rangle\in\mathtt{CFG}(\{a,b\})^3\mid\mathcal{L}(G_1)\cap\mathcal{L}(G_2)\neq\emptyset\;\wedge\;\mathcal{L}(G_2)\cap\mathcal{L}(G_3)\neq\emptyset\;\wedge\;\mathcal{L}(G_1)\cap\mathcal{L}(G_3)=\emptyset\}
{⟨
g
1
,
g
2
⟩
∈
CFG
({
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
=
∅
}
≤
{⟨
G
1
,
G
2
,
G
3
⟩
∈
CFG
({
a
,
b
}
)
3
∣
L
(
G
1
)
∩
L
(
G
2
)
=
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
=
∅
∧
L
(
G
1
)
∩
L
(
G
3
)
=
∅
}
{
⟨
g
1
,
g
2
⟩
∈
C
F
G
(
{
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
≠
∅
}
≤
{
⟨
G
1
,
G
2
,
G
3
,
G
4
⟩
∣
L
(
G
1
)
∩
L
(
G
2
)
≠
∅
∧
L
(
G
3
)
∩
L
(
G
4
)
≠
∅
∧
L
(
G
1
)
∩
L
(
G
4
)
=
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
=
∅
}
\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)\neq\emptyset\}\quad\leq\quad\{\langle G_1,G_2,G_3,G_4\rangle\mid\mathcal{L}(G_1)\cap\mathcal{L}(G_2)\neq\emptyset\;\wedge\;\mathcal{L}(G_3)\cap\mathcal{L}(G_4)\neq\emptyset\;\wedge\;\mathcal{L}(G_1)\cap\mathcal{L}(G_4)=\emptyset\;\wedge\;\mathcal{L}(G_2)\cap\mathcal{L}(G_3)=\emptyset\}
{⟨
g
1
,
g
2
⟩
∈
CFG
({
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
=
∅
}
≤
{⟨
G
1
,
G
2
,
G
3
,
G
4
⟩
∣
L
(
G
1
)
∩
L
(
G
2
)
=
∅
∧
L
(
G
3
)
∩
L
(
G
4
)
=
∅
∧
L
(
G
1
)
∩
L
(
G
4
)
=
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
=
∅
}
{
⟨
g
1
,
g
2
⟩
∈
C
F
G
(
{
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
≠
∅
}
≤
{
⟨
G
1
,
G
2
,
G
3
,
G
4
⟩
∈
C
F
G
(
{
a
,
b
}
)
4
∣
L
(
G
1
)
∩
L
(
G
2
)
≠
∅
∧
L
(
G
3
)
∩
L
(
G
4
)
≠
∅
∧
L
(
G
1
)
∩
L
(
G
4
)
=
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
=
∅
}
\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)\neq\emptyset\}\quad\leq\quad\{\langle G_1,G_2,G_3,G_4\rangle\in\mathtt{CFG}(\{a,b\})^4\mid\mathcal{L}(G_1)\cap\mathcal{L}(G_2)\neq\emptyset\;\wedge\;\mathcal{L}(G_3)\cap\mathcal{L}(G_4)\neq\emptyset\;\wedge\;\mathcal{L}(G_1)\cap\mathcal{L}(G_4)=\emptyset\;\wedge\;\mathcal{L}(G_2)\cap\mathcal{L}(G_3)=\emptyset\}
{⟨
g
1
,
g
2
⟩
∈
CFG
({
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
=
∅
}
≤
{⟨
G
1
,
G
2
,
G
3
,
G
4
⟩
∈
CFG
({
a
,
b
}
)
4
∣
L
(
G
1
)
∩
L
(
G
2
)
=
∅
∧
L
(
G
3
)
∩
L
(
G
4
)
=
∅
∧
L
(
G
1
)
∩
L
(
G
4
)
=
∅
∧
L
(
G
2
)
∩
L
(
G
3
)
=
∅
}
{
⟨
g
1
,
g
2
⟩
∈
C
F
G
(
{
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
≠
∅
}
≤
{
⟨
G
1
,
G
2
⟩
∣
∣
L
(
G
1
)
∩
L
(
G
2
)
∣
≥
2
}
\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)\neq\emptyset\}\quad\leq\quad\{\langle G_1,G_2\rangle\mid|\mathcal{L}(G_1)\cap\mathcal{L}(G_2)|\geq 2\}
{⟨
g
1
,
g
2
⟩
∈
CFG
({
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
=
∅
}
≤
{⟨
G
1
,
G
2
⟩
∣
∣
L
(
G
1
)
∩
L
(
G
2
)
∣
≥
2
}
{
⟨
g
1
,
g
2
⟩
∈
C
F
G
(
{
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
≠
∅
}
≤
{
⟨
G
1
,
G
2
⟩
∈
C
F
G
(
{
a
,
b
}
)
2
∣
∣
L
(
G
1
)
∩
L
(
G
2
)
∣
≥
2
}
\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)\neq\emptyset\}\quad\leq\quad\{\langle G_1,G_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid|\mathcal{L}(G_1)\cap\mathcal{L}(G_2)|\geq 2\}
{⟨
g
1
,
g
2
⟩
∈
CFG
({
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
=
∅
}
≤
{⟨
G
1
,
G
2
⟩
∈
CFG
({
a
,
b
}
)
2
∣
∣
L
(
G
1
)
∩
L
(
G
2
)
∣
≥
2
}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
a
,
b
,
c
}
∗
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{a,b,c\}^*\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
a
,
b
,
c
}
∗
}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
=
L
(
G
2
)
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{\langle G_1,G_2\rangle\mid\mathcal{L}(G_1)=\mathcal{L}(G_2)\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
=
L
(
G
2
)}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
⊆
L
(
G
2
)
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{\langle G_1,G_2\rangle\mid\mathcal{L}(G_1)\subseteq\mathcal{L}(G_2)\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
⊆
L
(
G
2
)}
{
⟨
g
1
,
g
2
⟩
∈
C
F
G
(
{
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
=
∅
}
≤
{
⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
⊆
L
(
G
2
)
‾
}
\{\langle g_1,g_2\rangle\in\mathtt{CFG}(\{a,b\})^2\mid\mathcal{L}(g_1)\cap\mathcal{L}(g_2)=\emptyset\}\quad\leq\quad\{\langle G_1,G_2\rangle\mid\mathcal{L}(G_1)\subseteq\overline{\mathcal{L}(G_2)}\}
{⟨
g
1
,
g
2
⟩
∈
CFG
({
a
,
b
}
)
2
∣
L
(
g
1
)
∩
L
(
g
2
)
=
∅
}
≤
{⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
⊆
L
(
G
2
)
}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
‾
⊆
L
(
G
2
)
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{\langle G_1,G_2\rangle\mid\overline{\mathcal{L}(G_1)}\subseteq\mathcal{L}(G_2)\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
⊆
L
(
G
2
)}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
‾
⊆
L
(
G
2
)
‾
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{\langle G_1,G_2\rangle\mid\overline{\mathcal{L}(G_1)}\subseteq\overline{\mathcal{L}(G_2)}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{⟨
G
1
,
G
2
⟩
∣
L
(
G
1
)
⊆
L
(
G
2
)
}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
a
:
w
∈
{
a
,
b
}
∗
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{wa : w\in\{a,b\}^*\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
a
:
w
∈
{
a
,
b
}
∗
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
a
a
:
w
∈
{
a
,
b
}
∗
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{waa : w\in\{a,b\}^*\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
aa
:
w
∈
{
a
,
b
}
∗
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
a
,
b
}
∗
−
{
λ
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{a,b\}^*-\{\lambda\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
a
,
b
}
∗
−
{
λ
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
a
,
b
}
∗
−
{
a
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{a,b\}^*-\{a\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
a
,
b
}
∗
−
{
a
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
a
,
b
}
∗
−
{
a
b
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{a,b\}^*-\{ab\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
a
,
b
}
∗
−
{
ab
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
a
,
b
}
∗
:
∣
w
∣
a
≥
1
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{w\in\{a,b\}^* : |w|_a\geq 1\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
a
,
b
}
∗
:
∣
w
∣
a
≥
1
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
a
,
b
}
∗
:
∣
w
∣
a
a
≥
1
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{w\in\{a,b\}^* : |w|_{aa}\geq 1\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
a
,
b
}
∗
:
∣
w
∣
aa
≥
1
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
a
,
b
}
∗
:
∣
w
∣
a
=
∣
w
∣
b
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{w\in\{a,b\}^* : |w|_a=|w|_b\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
a
,
b
}
∗
:
∣
w
∣
a
=
∣
w
∣
b
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
a
,
b
}
∗
:
∣
w
∣
a
≠
∣
w
∣
b
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{w\in\{a,b\}^* : |w|_a\neq|w|_b\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
a
,
b
}
∗
:
∣
w
∣
a
=
∣
w
∣
b
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
3
N
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{w\in\{0,1\}^* \mid \mathtt{value}_2(w) \in 3\mathbb{N}\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
3
N
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
3
N
+
1
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{w\in\{0,1\}^* \mid \mathtt{value}_2(w) \in 3\mathbb{N}+1\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
3
N
+
1
}}
{
g
∈
C
F
G
(
{
a
,
b
}
)
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
0
,
1
}
∗
∣
v
a
l
u
e
2
(
w
)
∈
3
N
+
2
}
}
\{g\in\mathtt{CFG}(\{a,b\})\mid\mathcal{L}(g)=\{a,b\}^*\}\quad\leq\quad\{G\mid\mathcal{L}(G)=\{w\in\{0,1\}^* \mid \mathtt{value}_2(w) \in 3\mathbb{N}+2\}\}
{
g
∈
CFG
({
a
,
b
})
∣
L
(
g
)
=
{
a
,
b
}
∗
}
≤
{
G
∣
L
(
G
)
=
{
w
∈
{
0
,
1
}
∗
∣
value
2
(
w
)
∈
3
N
+
2
}}