Prove $L$ is context free if $L_1$, $L_2$, $L_3$ are regular by building a suitable grammar

80 Views Asked by At

Given $L_1$, $L_2$, $L_3$ are regular, prove that:

$$L=\{w_1w_2w_3\space|\space w_i\in L_i\space \land\space|w_1|+|w_2|=|w_3| \}$$ is context free by building a suitable context free grammar. I know that each $L_i$ has Gi- a linear right or linear left grammar that creates it, and i thought of using it like so(it'll be a bit informal):
We'll define a set of deriving rules like so:
$P_{i,k}=\{P\in Gi\space|\space $there exist a chain of derivations starting is Si and ending with $w :|w|=k\}$
And define a set of deriving rules for G, that grammar that creates L:
$$P=\{P_{1,|w1|},P_{2,|w2|},P_{3,|w3|}| \exists wi\in L(Gi):|w1|+|w2|=|w3|\}\bigcup \{S->S_1S_2S_3\}$$
where Si are the starting variables of Gi and S of G. Will this work? or am i missing something?

1

There are 1 best solutions below

2
On BEST ANSWER

As far as I understand the solution you propose, I think it will not work. Already with the rule $S\rightarrow S_1S_2S_3$ you loose any chance to use the three regular grammars in a coordinated kind of way.

A possible solution is this: from the point between $w_2$ and $w_3$ you generate $w_3$ from right to left and $w_1w_2$ from left to right. So you want a left-linear grammar for $L_3$, right-linear grammars for the other two. In every step you generate exactly one terminal of $w_3$ and one of $w_1w_2$. Thus in the end the two parts are of equal length.

Formally, let $G_i := [N_i,T_i,P_i,S_i]$ be the regular grammars for the three languages, where $G_3$ is left-linear, the other two right linear. Further, every production generates exactly one terminal, and the sets of non-terminals are disjoint.

The new grammar is $$[(N_1\times N_3) \cup (N_2 \times N_3), T_1\cup T_2 \cup T_3, P, [S_1S_3]]$$ where $$P:= \{[XY]\rightarrow u[ZW]v : X\rightarrow uZ\in P_1\cup P_2 \wedge Y\rightarrow Wv \in P_3\}\} \cup$$ $$ \{ [XY]\rightarrow u[S_2W]v : X\rightarrow u\in P_1 \wedge Y\rightarrow Wv \in P_3 \} \cup $$ $$\{ [XY]\rightarrow uv : X\rightarrow u\in P_2 \wedge Y\rightarrow v \in P_3 \}.$$ The second component of the rule set switches from $G_1$ to $G_2$ when a terminating rule (without further non-terminal) from $G_1$ is applied. The last component terminates the derivation. $u$ and $v$ are always single terminals.