Arjun Suresh (talk | contribs) (→Solution) |
Arjun Suresh (talk | contribs) |
||
| Line 10: | Line 10: | ||
d)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{x | xx ∊ A\}</math> | d)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{x | xx ∊ A\}</math> | ||
| − | === | + | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== |
We can get a DFA for <math>L = \{x | xx ∊ A\}</math> as follows: | 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$. | Take DFA for <math>A</math> $(Q, \delta, \Sigma, S, F)$ with everything same except initially making $F = \phi$. | ||
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>
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 checking 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..
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>
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 checking 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..
GATECSE