1
$\begingroup$

Here's the question:

Given $L_A$ and $L_B$ are two regular languages over the alphabet $\sum=\{1,2,3\}$, is the following $L$ language context free? Prove your answer.
$L = \{w\in L_A \mid \exists x\in L_B \text{ such that }|x|=2|w|\}$

I would really appreciate any help in correcting my mistakes in formal writing as I feel that's where my weakness is.

My answer:
Intuition:

Language $L$ takes the words in $L_A$ and words if there's a word exactly double their length in $L_B$, the way I could prove $L$ is context-free is by building a pushdown automaton that accepts it using the DFA's of $L_A$ and $L_B$.
The automaton will have $2$ copies, which differ by a flag bit added to the states and delta function, $0$ for $L_A$ and $1$ for $L_B$, when reading a word in $L_A$ we will push $2$ $A's$ into the stack, and we stay in $0$ copy until we reach any state in $F_A$, where we have an opportunity to move to the copy of $L_B$ (setting the flag to $1$), where we will stay popping $A's$ (which will bring us to have words of double length when we see the bottom of the stack), then for every state in $F_B$, we will have an opportunity to remove the bottom of the stack if we see it (using epsilon).

Formal answer:

Both $L_A$,$L_B$ are regular, so there exists two DFA's, $A=(Q_A,\sum,\delta_A,q_{0A},F_A)$ and $B=(Q_B,\sum,\delta_B,q_{0B},F_B)$ where $L(A)=L_A$ and $L(B)=L_B$.

Notes: $S$ is stack bottom. $P$ accepts a language when stack is empty.
I will build a pushdown automaton $P=((Q_A\times\{0\})\cup (Q_B\times\{1\}), \sum, \{S,A\},\delta, (q_{0A},0),S,\phi)$.

For every $q\in Q_A$ and $\sigma\in \sum$:
$\delta((q,0),\sigma,S)=((\delta_A(q,\sigma),0), AAS)$
$\delta((q,0),\sigma,A)=((\delta_A(q,\sigma),0), AAA)$
For every $q\in F_A$:
$\delta((q,0),\epsilon,S)=((q_{0B},1),S)$
$\delta((q,0),\epsilon,A)=((q_{0B},1),A)$
For every $q\in Q_B$:
$\delta((q,1),\sigma,A)=((\delta_B(q,\sigma),1), \epsilon)$
For every $q\in F_B$:
$\delta((q,1),\epsilon,S)=((\delta_B(q,\epsilon),1), \epsilon)$. (I'm not sure how to write this.. all I want to say is accept the language by emptying the stack, do I need to put a state?).


Any help is really appreciated, thanks in advance.

$\endgroup$

1 Answer 1

1
$\begingroup$

The language $L$ is regular. This does not depend on the size of the alphabet, and it is also be true if $L_B$ is context-free. Let $\pi: \Sigma^* \to \Bbb N$ be the length map defined by $\pi(u) = |u|$. Observe that $$ L = L_A \cap \{ w \in \Sigma^* \mid 2|w| \in \pi(L_B)\}. $$ Since $L_B$ is context-free, the set $S = \pi(L_B)$ is a semilinear set. I let you verify that the set $$ T = \{n \in \Bbb N \mid 2n \in S\} $$ is also a semilinear set. Now, $$ L = L_A \cap \pi^{-1}(T) $$ and thus $L$ is regular.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .