Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| (77 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | == | + | ==Given a description of a language $L$, how to find the class of $L$?== |
| − | + | Find the set of strings generated by $L$ | |
| + | # If the set of strings in $L$ is finite, $L$ is regular since all finite languages are regular | ||
| + | # If the set of strings in $L$ is infinite, check if we can draw an NFA for recognizing $L$. If so, $L$ is regular | ||
| + | # If $NFA$ is not possible for $L$, check if we can recognize $L$ using a $PDA$, that is with a stack in addition to set of states. If so, $L$ is $CFL$. | ||
| + | # If the moves of $PDA$ are all deterministic, then $L$ is a $DCFL$ | ||
| + | # If $PDA$ is not possible for $L$, see if we can get a $TM$ for $L$ | ||
| + | # If $TM$ takes only a linear space (in terms of length of input string), then $L$ is $CSL$. otherwise its just recursive | ||
| + | # If $L$ is a decision problem and $TM$ can just say "yes" and may not halt in case of "no", then $L$ is recursively enumerable (partially decidable). | ||
| + | #If $TM$ can say both "yes" and "no" then $L$ is recursive | ||
| + | # If no $TM$ is possible for $L$, then $L$ is undecidable | ||
| + | ==Some Facts== | ||
| + | *Partially undecidable or semi-undecidable is considered undecidable. For example halting problem is considered undecidable but is semi-decidable. | ||
| + | *$P$, $NP$ and $NPC$ problems can all be decided by a $TM$ and hence are recursive. | ||
| + | *All undecidable problems are NP-Hard, but all NP-Hard problems are not undecidable. | ||
| + | *Turing decidable problems are recursive but Turing recognizable (Turing acceptable) problems are only recursively enumerable. | ||
| − | ===2. $L = \{wxw | + | ==Some Twisted Examples== |
| − | + | ||
| − | + | ||
| + | ===1. $L = \{ww \mid w ∈ (a+b)^*\}$=== | ||
| + | The set of strings in $L$ are $\{aa, bb, aaaa, abab, baba, bbbb, aaaaaa, ...\}$. We cannot accept these strings using an $NFA$. Now, even a $PDA$ is not possible as once we store $w$ on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize $L$. Now, $L$ can be accepted by a $TM$ in linear space and hence $L$ is $CSL$. | ||
| + | |||
| + | ===2. $L = \{ww\mid w ∈ (a+b)^+\}$=== | ||
| + | Same explanation as above, $L$ is $CSL$. | ||
| + | |||
| + | ===3. $L = \{ww_R\mid w ∈ ({a+b})^*\}$=== | ||
| + | $ww_R$ can be accepted by a $PDA$ and hence is $CFL$. But we need a $NPDA$ for this as there is no deterministic way to identify where $w$ ends and $w_R$ starts. $wcw_R, w\in(a+b)^*$ is accepted by a $DPDA$ and hence is $DCFL$. | ||
| + | |||
| + | ===4. $L = \{ww_R\mid w ∈ ({a+b})^+\}$=== | ||
| + | Same explanation as above. $L$ is $CFL$. | ||
| + | |||
| + | ===5. $L = \{wxw \mid w,x ∈ ({a+b})^*\} $=== | ||
| + | $L$ is regular since $ L = \Sigma^*$, by making $x = (a+b)^*$ and $w = \epsilon$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$ | ||
| + | |||
| + | This language is different from the $L = \{wcw \mid w ∈ ({a,b})^*\} $ which is clearly a CSL. Here, we cannot do any reduction and hence there is no way to accept a string without checking w before c and w after c are the same which requires an LBA. | ||
| + | |||
| + | ===6. $L = \{wxw\mid w,x ∈ ({a+b})^+\}$=== | ||
| + | $L$ doesn't contain all strings in $\Sigma^*$ as the strings like $abab$ are not contained in $L$. All words starting and ending in $a$ or starting and ending in $b$ are in $L$. But $L$ also contains words starting with $a$ and ending in $b$ like $abbab, aabbbabaab$ etc where the starting sub-string exactly matches the ending sub-string and at least a letter separates them. To accept such strings we need a $TM$ with linear space (this is at least as hard as accepting $ww, w \in (a+b)^*$), making $L$, a $CSL$. | ||
| + | |||
| + | ===7. $L = \{wxw_R\mid w,x ∈ ({a+b})^*\}$=== | ||
| + | $L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*, making L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$ | ||
| + | |||
| + | This language is different from the $L = \{wcw_R \mid w ∈ \{{a,b}\}^*\} $ which is clearly a DCFL. Here, we cannot do any reduction and hence there is no way to accept a string without checking that the string after c is the reverse of the string before c, which requires a DPDA. | ||
| + | |||
| + | ===8. $L = \{wxw_R\mid w,x ∈ ({a+b})^+\}$=== | ||
| + | The set of strings in $L$ are $\{aaa, aba, aaaa, aaba, abaa, abba, baab, ...\}$ i.e.; $L$ contains all strings starting and ending with $a$ or starting and ending with $b$ and containing at least 3 letters. Moreover, $L$ doesn't contain any other strings. Thus $L$ can be accepted by a finite automata making $L$ regular . Regular expression for $L$ is $a(a+b)^+a + b(a+b)^+b$. | ||
| + | |||
| + | ===9. $L = \{wxwy \mid w,x,y ∈ ({a+b})^+\}$=== | ||
| + | For any string to be in $L$, the beginning part of the string ($w$) must repeat at some other point (between the second and last characters) of the string (next $w$). Since $y$ is there at the end which can generate any string, we can make $w$ as small as possible as per the given condition. So, $w$ can be either $a$ or $b$. We can thus write regular expression for $L$ as $a(a+b)^+a(a+b)^+ + b(a+b)^+b(a+b)^+$ | ||
| + | |||
| + | ===10. $L = \{xwyw \mid w,x,y ∈ ({a+b})^+\}$=== | ||
| + | Similar explanation for example 9, except that instead of first character being $a$ or $b$ we have the last character. So, regular expression for $L$ will be | ||
| + | $(a+b)^+a(a+b)^+a + (a+b)^+b(a+b)^+b$ | ||
| + | |||
| + | |||
| + | ===11. $L = \{wxyw \mid w,x,y ∈ ({a+b})^+\}$=== | ||
| + | Here, $w$ is coming at the beginning and also at the end. Unlike as in example 8 or 9, we cannot restrict $w$ to be $a$ or $b$ as a string starting with $a$ can end in $b$ and still be in $L$- example $abaaab$, where $w = ab$ and $x,y = a$. In short we need to compare the substring at the beginning of the string with that at the end, making this a CSL. | ||
| + | |||
| + | ===12. $L = \{xww \mid w,x ∈ ({a+b})^*\}$=== | ||
| + | $L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*$, making $L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$ | ||
| + | |||
| + | ===13. $L = \{xww \mid w,x ∈ ({a+b})^+\}$=== | ||
| + | Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of an LBA making $L$ a CSL. | ||
| + | |||
| + | ===14. $L = \{xww_R \mid w,x ∈ ({a+b})^+\}$=== | ||
| + | Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of a PDA making $L$ a NCFL (non-determinism is required to guess the start of $w$). | ||
| + | |||
| + | {{Template:FBD}} | ||
| + | |||
| + | [[Category: Automata Theory Notes]] | ||
| + | |||
| + | [[Category: Compact Notes for Reference of Understanding]] | ||
Find the set of strings generated by $L$
The set of strings in $L$ are $\{aa, bb, aaaa, abab, baba, bbbb, aaaaaa, ...\}$. We cannot accept these strings using an $NFA$. Now, even a $PDA$ is not possible as once we store $w$ on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize $L$. Now, $L$ can be accepted by a $TM$ in linear space and hence $L$ is $CSL$.
Same explanation as above, $L$ is $CSL$.
$ww_R$ can be accepted by a $PDA$ and hence is $CFL$. But we need a $NPDA$ for this as there is no deterministic way to identify where $w$ ends and $w_R$ starts. $wcw_R, w\in(a+b)^*$ is accepted by a $DPDA$ and hence is $DCFL$.
Same explanation as above. $L$ is $CFL$.
$L$ is regular since $ L = \Sigma^*$, by making $x = (a+b)^*$ and $w = \epsilon$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$
This language is different from the $L = \{wcw \mid w ∈ ({a,b})^*\} $ which is clearly a CSL. Here, we cannot do any reduction and hence there is no way to accept a string without checking w before c and w after c are the same which requires an LBA.
$L$ doesn't contain all strings in $\Sigma^*$ as the strings like $abab$ are not contained in $L$. All words starting and ending in $a$ or starting and ending in $b$ are in $L$. But $L$ also contains words starting with $a$ and ending in $b$ like $abbab, aabbbabaab$ etc where the starting sub-string exactly matches the ending sub-string and at least a letter separates them. To accept such strings we need a $TM$ with linear space (this is at least as hard as accepting $ww, w \in (a+b)^*$), making $L$, a $CSL$.
$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*, making L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$
This language is different from the $L = \{wcw_R \mid w ∈ \{{a,b}\}^*\} $ which is clearly a DCFL. Here, we cannot do any reduction and hence there is no way to accept a string without checking that the string after c is the reverse of the string before c, which requires a DPDA.
The set of strings in $L$ are $\{aaa, aba, aaaa, aaba, abaa, abba, baab, ...\}$ i.e.; $L$ contains all strings starting and ending with $a$ or starting and ending with $b$ and containing at least 3 letters. Moreover, $L$ doesn't contain any other strings. Thus $L$ can be accepted by a finite automata making $L$ regular . Regular expression for $L$ is $a(a+b)^+a + b(a+b)^+b$.
For any string to be in $L$, the beginning part of the string ($w$) must repeat at some other point (between the second and last characters) of the string (next $w$). Since $y$ is there at the end which can generate any string, we can make $w$ as small as possible as per the given condition. So, $w$ can be either $a$ or $b$. We can thus write regular expression for $L$ as $a(a+b)^+a(a+b)^+ + b(a+b)^+b(a+b)^+$
Similar explanation for example 9, except that instead of first character being $a$ or $b$ we have the last character. So, regular expression for $L$ will be $(a+b)^+a(a+b)^+a + (a+b)^+b(a+b)^+b$
Here, $w$ is coming at the beginning and also at the end. Unlike as in example 8 or 9, we cannot restrict $w$ to be $a$ or $b$ as a string starting with $a$ can end in $b$ and still be in $L$- example $abaaab$, where $w = ab$ and $x,y = a$. In short we need to compare the substring at the beginning of the string with that at the end, making this a CSL.
$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*$, making $L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$
Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of an LBA making $L$ a CSL.
Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of a PDA making $L$ a NCFL (non-determinism is required to guess the start of $w$).
Here, <math>L</math> can generate all strings in <math>\Sigma^*</math>, by making <math>x = (a+b)^*</math> and <math>w = \epsilon</math>. Hence, <math>L</math> is regular.
Here, our problem is this- given a word s, whether it belongs to L or not. I say that a word belongs to L, iff it starts and end with a or starts and ends with b (and contains at least 3 letters in total). Now, in case of wxw, the same logic won't work. As you told if s ∈ {a (a+b)^+ a} U {b (a+b)^+ b}, then its of the form wxw. But if s ∉ {a (a+b)^+ a} U {b (a+b)^+ b}, we can't say its not of the form wxw. For example, take s as abbab, its of the form wxw with w = "ab" and x = "b". Thus the reduction will work only one way and hence it cannot be used.
GATECSE