(Solution)
Line 1: Line 1:
  
Let Σ = {a, b, c}. Which of the following statements is true ?
+
Let <math>Σ = {a, b, c}</math>. Which of the following statements is true ?
  
a)For any A ⊆ Σ*, if A is regular, then so is {xx | x ∊ A}
+
a)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{xx | x ∊ A\}</math>
  
'''b)For any A ⊆ Σ*, if A is regular, then so is {x | xx ∊ A}'''
+
'''b)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{x | xx ∊ A\}</math>'''
  
c)For any A ⊆ Σ*, if A is context-free, then so is {xx | x ∊ A}
+
c)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{xx | x ∊ A\}</math>
  
d)For any A ⊆ Σ*, if A is context-free, then so is {x | xx ∊ A}
+
d)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{x | xx ∊ A\}</math>
  
 
===Solution===
 
===Solution===
We can get a DFA for L = {x | xx ∊ A} as follows:
+
We can get a DFA for <math>L = \{x | xx ∊ A\}</math> as follows:
Take DFA for A $(Q, \delta, \Sigma, S, F)$ with everything same except initially making F = {}.  
+
Take DFA for <math>A</math> $(Q, \delta, \Sigma, S, F)$ 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.  
+
Now for each state $D \in Q$, consider 2 separate DFAs, one with <math>S</math> as the start state and <math>D</math> as the final state and another with <math>D</math> as the start state and set of final states $⊆ F$. If both these DFAs accept same language make <math>D</math> as final state.  
  
 
This procedure works as the equivalence of 2 DFAs is decidable.
 
This procedure works as the equivalence of 2 DFAs is decidable.
Line 19: Line 19:
 
'''Contradictions for other choices'''
 
'''Contradictions for other choices'''
  
a) Consider A =  Σ*. Now for $w \in A,  L = \{xx | x \in A\} = \{ww | w \in Σ^*\} $ which is context sensitive
+
a) Consider <math>A =  Σ^*</math>. Now for $w \in A,  L = \{xx | x \in A\} = \{ww | w \in Σ^*\} $ which is context sensitive
  
 
c) Same example as for (a)
 
c) Same example as for (a)

Revision as of 02:22, 31 January 2014

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

a)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{xx | x ∊ A\}</math>

b)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{x | xx ∊ A\}</math>

c)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{xx | x ∊ A\}</math>

d)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{x | xx ∊ A\}</math>

Solution

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

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

Contradictions for other choices

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

c) Same example as for (a)

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








blog comments powered by Disqus

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

a)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{xx | x ∊ A\}</math>

b)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{x | xx ∊ A\}</math>

c)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{xx | x ∊ A\}</math>

d)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{x | xx ∊ A\}</math>

Solution[edit]

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

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

Contradictions for other choices

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

c) Same example as for (a)

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








blog comments powered by Disqus