The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+8 votes

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\}$

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\}$

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={a^{n}b^{n}c*a^{*}b^{m}c^{m} |n,m >=0} and we are making L from A as per the above option..I'm not getting how you derived a^{n}b^{n}c^{n} from A (this one is not in the form of xx)

Please clarify...

{x∣xx∊A}

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

+1

@Arjun Sir,

as you mentioned that a^{n}b^{n }c*a*b^{n}c^{n} is a CFL ..could you please explain how PDA recognizes this language..?

is it like pushing a^{n}b^{n }to stack and then pop for every b^{n}c^{n..? }

OR push a^{n}b^{n} skip c*and a* then push b^{n} and pop three times for every c...

Also I'm confused about how you derived a^{n}b^{n}c^{n} from the given language...please list the languages in the set { a^{n}b^{n }c*a*b^{n}c^{n, } 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^{n }) then the resulting string will be c*a* only ....isn't it... or am I missing something...Please clarify...

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 ?

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 488
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,203 questions

43,662 answers

124,117 comments

42,947 users