Identify the class of the language Revision as of 23:34, 17 February 2014 by Arjun Suresh (talk | contribs) (→‎Some Examples) (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Given a description of <math>L</math>, how to find the class of <math>L</math>?

Find the set of strings generated by <math>L</math>
If the set of strings in <math>L</math> is finite, <math>L</math> is regular since all finite languages are regular
If the set of strings in <math>L</math> is infinite, check if we can draw an NFA for recognizing <math>L</math>. If so, <math>L</math> is regular
If  <math>NFA</math> is not possible for <math>L</math>, check if we can recognize <math>L</math> using a <math>PDA</math>, that is with a stack in addition to set of states. If so, <math>L</math> is <math>CFL</math>.
If the moves of <math>PDA</math> are all deterministic, then <math>L</math> is a <math>DCFL</math>
If <math>PDA</math> is not possible for <math>L</math>, see if we can get a <math>TM</math> for <math>L</math>
If <math>TM</math> takes only a linear space (in terms of length of input string), then <math>L</math> is <math>CSL</math>. otherwise its just recursive
If <math>L</math> is a decision problem and TM can just say "yes" and may not halt in case of "no", then <math>L</math> is recursively enumerable (partially decidable). If <math>TM</math> can say both "yes" and "no" then <math>L</math> is recursive
If no <math>TM</math> is possible for <math>L</math>, then <math>L</math> is undecidable

Some Facts

Partially undecidable or semi-undecidable is under undecidable class. For example halting problem is recursively enumerable but is undecidable
<math>P</math>, <math>NP</math> and <math>NPC</math> problems can all be decided by a <math>TM</math> and hence are recursive. 
All undecidable problems are NP-Hard, but all NP-Hard problems are not undecidable

Some Examples

1. $L = \{ww| w ∈ \{{a,b}\}^*\}$

The set of strings in <math>L</math> are <math>\{aa, bb, aaaa, abab, baba, bbbb, aaaaaa, ...\}</math>. We cannot accept these strings using an <math>NFA</math>. Now, even a <math>PDA</math> is not possible as once we store <math>w</math> on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize <math>L</math>. <math>L</math> can be accepted by a <math>TM</math> in linear space and hence <math>L</math> is <math>CSL</math>.

2. $L = \{ww| w ∈ \{{a,b}\}^+\}$

Same explanation as above, <math>L</math> is <math>CSL</math>.

3. $L = \{ww_R| w ∈ \{{a,b}\}^*\}$

<math>ww_R</math> can be accepted by a <math>PDA</math> and hence is <math>CFL</math>. But we need a <math>NPDA</math> for this as there is no deterministic way to identify where <math>w</math> ends and <math>w_R</math> starts. <math>wcw_R, w\in(a+b)^*</math> is accepted by a <math>DPDA</math> and hence is <math>DCFL</math>.

4. $L = \{ww_R| w ∈ \{{a,b}\}^+\}$

Same explanation as above. <math>L</math> is <math>CFL</math>.

5. $L = \{wxw | w,x ∈ \{{a,b}\}^*\} $

<math>L</math> is regular since <math> L = \Sigma^*</math>, by making <math>x = (a+b)^*</math> and <math>w = \epsilon</math>.

6. $L = \{wxw| w,x ∈ \{{a,b}\}^+\}$

<math>L</math> doesn't contain all strings in <math>\Sigma^*</math> as the strings like <math>abab</math> are not contained in <math>L</math>. All words starting and ending in <math>a</math> or starting and ending in <math>b</math> are in <math>L</math>. But <math>L</math> also contains words starting with <math>a</math> and ending in <math>b</math> like <math>abbab, aabbbabaab</math> 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 an <math>LBA</math> (this is at least as hard as accepting <math>ww, w \in (a+b)^*</math>), making <math>L</math>, a <math>CSL</math>.

7. $L = \{wxw_R| w,x ∈ \{{a,b}\}^*\}$

<math>L</math> is regular. Since, <math>w</math> can be <math>\epsilon</math> and <math>x \in (a+b)^*, L =\Sigma^*</math>.

8. $L = \{wxw_R| w,x ∈ \{{a,b}\}^+\}$

<math>L</math> is regular. <math>L</math> contains all strings starting and ending with <math>a</math> or starting and ending with <math>b</math> and containing at least 3 letters. Moreover, <math>L</math> doesn't contain any other strings. Thus <math>L</math> can be accepted by a <math>DFA</math>. Regular expression for <math>L</math> is <math>a(a+b)^+a + b(a+b)^+b</math>.

Tweet