1,346 views
4 votes
4 votes

 This DFA accepts a certain language L. In this problem we shall consider certain other languages that are defined by their tails, that is, languages of the form (0+1)*w, for some particular string w of 0's and 1's. Call this language L(w). Depending on w, L(w) may be contained in L, disjoint from L, or neither contained nor disjoint from L (i.e., some strings of the form xw are in L and others are not).

Your problem is to find a way to classify w into one of these three cases. Then, use your knowledge to classify the following languages:

  1. L(1111001), i.e., the language of regular expression (0+1)*1111001.
  2. L(11011), i.e., the language of regular expression (0+1)*11011.
  3. L(110101), i.e., the language of regular expression (0+1)*110101.
  4. L(00011101), i.e., the language of regular expression (0+1)*00011101.

These are the options:

       A). L(1111001) is disjoint from L.

       B). L(110101) is contained in L.

       C). L(1111001) is contained in L.

       D). L(110101) is disjoint from L.

1 Answer

4 votes
4 votes

Someone is preparing for GATE with good questions :)

Here, $L(w)$ is defined for a given $w$. For example;

  • $L(1111001) = \{1111001, 01111001, 11111001, \ldots\}$

Now, if $w$ is in $L$, $L(w)$ and $L$ will have at least one common string which is $w$. But if $w$ is not in $L$, $L(w)$ and $L$ can contain common strings -- take $w = 1$ which is not in $L$ but $111$ is in $L$ as well as $L(w)$.

Here, $L$ describes the set of binary strings with at least three $1's$ and for every $0$, there is a $1$ following it.

Now lets see the options:

  • $L(1111001):$ Here $w$ is not in $L$. Because to reach the final state, for each '0' there must be at least one '1' following it. For the same reason if we add any prefix to $w$, it will still be not in $L$. So, $L$ and $L(w)$ are disjoint here.
  • $L(110101):$ Here $w$ is not in $L$ but if we prefix a $1$ to $w$, $1w$ is in $L$. So, $L$ and $L(w)$ are not disjoint and $L(w)$ is not contained in $L$.

So, option A is true and all others are false.

Answer:

No related questions found