+8 votes
498 views

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\}$
asked
retagged | 498 views
0
0

@Arjun sir,

the option d) if A is context-free then so is {x | xx∈A} ..Here A should be split up into two equal parts (ie: x) in such a way that x is context-free.

In your answer A={anbnc*a*bmcm |n,m >=0} and we are making L from A as per the above option..I'm not getting how you derived anbncn from A (this one is not  in the form of xx)

Please clarify...

{xxxA}

## 1 Answer

+10 votes
Best answer

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..

answered by Veteran (400k points)
edited by
+1

@Arjun Sir,

as you mentioned that anbc*a*bncn is a CFL ..could you please explain how PDA recognizes this language..?

is it like pushing anbto stack and then pop for every bncn..?

OR push anbn skip c*and a* then push bn and pop three times for every c...

Also I'm confused about how you derived anbncn from the given language...please list the languages in the set { anbc*a*bncn,  n>=0}....

the value of n at a time is applicable to all the a's b's and c's ..right...? so if n=0 (in our case , in order to nullify b) then the resulting string will be c*a* only ....isn't it... or am I missing something...Please clarify...

0
yes, guess I made a mistake- have corrected now. You can now see the strings in A and L.
0

In the d part we have xx so how can you take a^n b^n c* a*b^m c^m ?

although it seems to be same but the value of m and n can vary so how can they be both same ?

+1
$A$ can be any CFL as per D. Now, we only consider strings of the form $xx$ in $A$.
0

@Arjun sir,

the option d) if A is context-free then so is {x | xx∈A} ..Here A should be split up into two equal parts (ie: x) in such a way that x is context-free.

In your answer A={anbnc*a*bmcm |n,m >=0} and we are making L from A as per the above option..I'm not getting how you derived anbncn from A (this one is not  in the form of xx)

Please clarify...

+5

$A$ ,can be any CFL , need not to be in form of $xx$, those strings in form of $xx$ in $A$, we are taking $x$ from them.

so out of $a^nb^nc^*a^*b^mc^m$, only those we need to take in which first half is exactly as second half such as $xx$ will be $abcabc$ or $aabbccaabbcc,....$ etc then $x$ will be $abc, aabbcc,...$ so on

+1 vote
1 answer
3
+2 votes
2 answers
5
0 votes
2 answers
7