Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 1: | Line 1: | ||
| + | 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\}$ | |
| − | |||
| − | d)For any | ||
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== | ||
| − | We can get a DFA for | + | We can get a DFA for $L = \{x | xx ∊ A\}$ as follows: |
| − | Take DFA for | + | Take DFA for $A$ $(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 | + | 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. | This procedure works as checking the equivalence of 2 DFAs is decidable. | ||
| Line 19: | Line 18: | ||
'''Contradictions for other choices''' | '''Contradictions for other choices''' | ||
| − | a) Consider | + | 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) | c) Same example as for (a) | ||
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\}$
We can get a DFA for $L = \{x | xx ∊ A\}$ as follows: Take DFA for $A$ $(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.
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 | 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 $Σ = \{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\}$
We can get a DFA for $L = \{x | xx ∊ A\}$ as follows: Take DFA for $A$ $(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.
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 | 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