retagged by
1,192 views
9 votes
9 votes

Let $Σ = \{a, b, c\}$. Which of the following statements is true?

  1. For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{xx \mid x ∊ A\}$
  2. For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{x \mid xx ∊ A\}$
  3. For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{xx \mid x ∊ A\}$
  4. For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{x \mid xx ∊ A\}$
retagged by

1 Answer

Best answer
10 votes
10 votes

We can get a DFA for $L = \{x \mid xx ∊ A\}$ as follows:
Take DFA for $A$ $\left(Q, \delta, \Sigma, S, F\right)$ with everything same except initially making $F = \phi$.
Now for each state $D \in Q$, consider 2 separate DFAs, one with $S$ as the start state and $D$ as the final state and another with $D$ as the start state and set of final states $⊆ F$. If both these DFAs accept same language make $D$ as final state.

This procedure works as checking the equivalence of 2 DFAs is decidable.

Contradictions for other choices


a) Consider $A =  Σ^* $. Now for $ w \in A,  L = \{xx \mid x \in A\} = \{ww \mid w \in Σ^*\} $ which is context sensitive

c) Same example as for (a)

d) Consider $A =  \{a^nb^n c^* a^*b^mc^m  \mid n, m \ge 0\} $
This is CFL. But if we make $L$ from $A$ as per (d), it'll be
$L = \{a^nb^nc^n \mid n \ge 0\}$ which is not context free..

edited by

Related questions