snippetMinor
How to split a context-free language into three sub-languages?
Viewed 0 times
threefreelanguagesintosublanguagesplithowcontext
Problem
I try to split the language
$$
L = \{a^ib^j \mid i \neq 2j, i \neq 3j\}
$$
into three languages
\begin{align}
L_1 &= \{a^ib^j \mid i 3j\}
\end{align}
and then use one more production $S = S_1|S_2|S_3$,
but I have no idea how to find the CFG for $L_2$.
$$
L = \{a^ib^j \mid i \neq 2j, i \neq 3j\}
$$
into three languages
\begin{align}
L_1 &= \{a^ib^j \mid i 3j\}
\end{align}
and then use one more production $S = S_1|S_2|S_3$,
but I have no idea how to find the CFG for $L_2$.
Solution
The idea is to start with a grammar for the related language $L'_2 = \{a^ib^j \mid 2j \leq i \leq 3j\}$:
$$ S \to a^2Sb \mid a^3Sb \mid \epsilon. $$
We want to force at least one production of the form $a^2Sb$ and at least one of the form $a^3Sb$. There are many ways of doing that. The simplest, probably, is to force one of these productions to be the first, and the other one to be the last:
$$ \begin{align} &S \to a^2 T b \\ & T \to a^2 T b \mid a^3 T b \mid a^3 b \end{align} $$
Alternatively, let us notice that the condition $2j < i < 3j$ can be written as $2j+1 \leq i \leq 3j-1$, and also as $2(j-2) \leq i-5 \leq 3(j-2)$. This implies the even simpler grammar
$$ S \to a^2Sb \mid a^3Sb \mid a^5 b^2 $$
$$ S \to a^2Sb \mid a^3Sb \mid \epsilon. $$
We want to force at least one production of the form $a^2Sb$ and at least one of the form $a^3Sb$. There are many ways of doing that. The simplest, probably, is to force one of these productions to be the first, and the other one to be the last:
$$ \begin{align} &S \to a^2 T b \\ & T \to a^2 T b \mid a^3 T b \mid a^3 b \end{align} $$
Alternatively, let us notice that the condition $2j < i < 3j$ can be written as $2j+1 \leq i \leq 3j-1$, and also as $2(j-2) \leq i-5 \leq 3(j-2)$. This implies the even simpler grammar
$$ S \to a^2Sb \mid a^3Sb \mid a^5 b^2 $$
Context
StackExchange Computer Science Q#115734, answer score: 2
Revisions (0)
No revisions yet.