edited by
1,544 views
3 votes
3 votes

Consider an alphabet $\Sigma=\{a,b\}.$

Let $L_{1}$ be the language given by the regular expression $(a+b)^{\ast}bb(a+b)^{\ast}$ and let $L_{2}$ be the language $baa^{\ast}b.$

Define $L:=\{u\in\Sigma^{\ast}\mid \exists w\in L_{2}\: s.t.\: uw\in L_{1}\}.$

  1. Give an example of a word in $L.$
  2. Give an example of a word not in $L.$
  3. Construct an NFA for $L.$
edited by

3 Answers

Best answer
8 votes
8 votes

Given $L_1,L_2$ on same Alphabet, here $\Sigma = \{ a,b \}$, The right quotient of $L_1$ with $L_2$ is

$L_1/L_2 = \{w: wx \in L_1 \,\, and\,\, x \in L_2 \} $

That is, the strings in $L_1/L_2$ are strings from $L_1$ "with their tails cut off." If some string of $L_1$ can be broken into two parts, $w$ and $x,$ where $x$ is in language $L_2,$ then $w$ is in language $L_1/L_2.$

Given $L : = \{ u \in \Sigma^*| \exists w \in L_2 \,\, s.t.\,\, uw \in L_1\}$ in the Question is nothing but $L_1/L_2.$

So, in order to find $L,$ we find $L_1/L_2 .$ 


$L_1/L_2 :$

In order to find $L_1/L_2$, we observe that strings in $L_2$ are $bab,baab,baaab,....etc.$ The thing to observe is that we don't have consecutive $b's$ in strings of $L_2.$ Now we know that If some string $w$ of $L_1$ can be broken into two parts, $u$ and $v,$ where $v$ is in language $L_2,$ then $u$ is in language $L_1/L_2.$ Now, for given $L_1,L_2,$ that breaking point of the strings of $L_1$ is definitely somewhere after the first $b$ of the consecutive $b's$ in the regular expression of $L_1.$ 

i.e. for any string $w \in L( (a+b)^*bb(a+b)^*)$, the breaking point of that string $w$ will be somewhere in the bold part of  (a+b)*bb(a+b)*.

With this observation, it can easily be seen that the regular expression for $L$ is $(a+b)^*bb(a+b)^* + (a+b)^*b.$

So, $r(L) = (a+b)^*bb(a+b)^* + (a+b)^*b. $


Answer (a) : $aaabbaa,aaab$

Answer (b) : $aaaa$

Answer (c) : NFA for $L :$

selected by
0 votes
0 votes
  1. u=b, w=bab  uw=bbab
    uw∈L1  hence b∈L

      [Note: L is collection of all such u’s]

      B. If u=∈  then there would be no w such that  uw∈L1

          hence ∈ does not belong to l

       C. (a+b)^*b

Related questions

2 votes
2 votes
3 answers
1
1 votes
1 votes
2 answers
2
1 votes
1 votes
1 answer
3