The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
465 views
Let $Σ = \{a, b, c\}$. Which of the following statements is true ?

a)For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{xx \mid x ∊ A\}$

b)For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{x \mid xx ∊ A\}$

c)For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{xx \mid x ∊ A\}$

d)For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{x \mid xx ∊ A\}$
asked in Theory of Computation by Boss (18.3k points)
retagged by | 465 views
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 (370k 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 

Related questions

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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,462 questions
49,920 answers
165,466 comments
65,898 users