(Solution)
(Solution)
Line 12: Line 12:
 
===Solution===
 
===Solution===
 
We can get a DFA for L = {x | xx ∊ A} as follows:
 
We can get a DFA for L = {x | xx ∊ A} as follows:
Take DFA for A. Let S be its start state.
+
Take DFA for A $(\delta, \sigma, D, F)$
 
For each state D of A, 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 final state in final states of A. If both these DFAs accept same language make D as final state.  
 
For each state D of A, 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 final state in final states of A. If both these DFAs accept same language make D as final state.  
  

Revision as of 02:13, 31 January 2014

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

a)For any A ⊆ Σ*, if A is regular, then so is {xx | x ∊ A}

b)For any A ⊆ Σ*, if A is regular, then so is {x | xx ∊ A}

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

d)For any A ⊆ Σ*, if A is context-free, then so is {x | xx ∊ A}

Solution

We can get a DFA for L = {x | xx ∊ A} as follows: Take DFA for A $(\delta, \sigma, D, F)$ For each state D of A, 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 final state in final states of A. If both these DFAs accept same language make D as final state.

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

Contradictions for other choices

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

c) Same example as for (a)

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








blog comments powered by Disqus

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

a)For any A ⊆ Σ*, if A is regular, then so is {xx | x ∊ A}

b)For any A ⊆ Σ*, if A is regular, then so is {x | xx ∊ A}

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

d)For any A ⊆ Σ*, if A is context-free, then so is {x | xx ∊ A}

Solution[edit]

We can get a DFA for L = {x | xx ∊ A} as follows: Take DFA for A $(\delta, \sigma, D, F)$ For each state D of A, 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 final state in final states of A. If both these DFAs accept same language make D as final state.

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

Contradictions for other choices

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

c) Same example as for (a)

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








blog comments powered by Disqus