search
Log In
0 votes
37 views

Consider the following regular expressions over alphabet$\{a,b\}$, where the notation $(a+b)^+$ means $(a+b)(a+b)^*$:

$$r_1=(a+b)^+a(a+b)^*$$

$$r_2=(a+b)^*b(a+b)^+$$

Let $L_1$ and $L_2$ be the languages defined by $r_1$ and $r_2$, respectively. Which of the following regular expressions define $L_1\cap L_2$?

  1. $(a+b)^+a(a+b)^*b(a+b)^+$
  2. $(a+b)^*a\;b(a+b)^*$
  3. $(a+b)^*b(a+b)^*a(a+b)^*$
  4. $(a+b)^*a(a+b)^*b(a+b)^*$
in Others
edited by
37 views

2 Answers

0 votes

C)The easiest way here is to check the minimum length string that is accepted by both $L_{1}$ & $L_{2}$, in this case it is “ba”, the only option which matches with that is C.

 

Long Method:

  1. Construct minimal DFA $D_{1}$ & $D_{2}$ for $L_{1}$ & $L_{2}$ respectively.
  2. Use product construction to combine 2 DFA’s and construct intersection of 2 DFA’s. Let Resultant DFA  $D_{1}\cap D_{2}=D_{r}$.
  3. Now, derive regular expression from DFA $D_{r}$.

edited by
0 votes

Answer:

Answer:

Related questions

3 votes
3 answers
1
67 views
Which of the following languages over the alphabet $\{0,1\}$ are $not$ recognized by deterministic finite state automata $(DFA)$ with $three$ states? Words which do not have $11$ as a contiguous subword Binary representations of multiples of three Words that have $11$ as a suffix Words that do not contain $101$ as a contiguous subword
asked Jan 28 in Others soujanyareddy13 67 views
0 votes
1 answer
2
33 views
Some children are given boxes containing sweets. Harish is happy if he gets either gems or toffees. Rekha is happy if she gets both bubble gums and peppermints. Some of the boxes are special, which means that if the box contains either gems or toffees, then it also contains ... we infer? Harish is happy No bubble gums in Rekha's box No toffees in Harish's box There are peppermints in Rekha's box
asked Jan 28 in Others soujanyareddy13 33 views
0 votes
1 answer
3
17 views
In a class, every student likes exactly one novelist and one musician. If two students like the same novelist, they also like the same musician. The class can be divided into novelist groups, each group consisting of all the students who like one novelist. Similarly, ... For every musician group, there is a bigger novelist group For every novelist group, there is a musician group of the same size
asked Jan 28 in Others soujanyareddy13 17 views
0 votes
1 answer
4
27 views
A boolean function on $n$ variables is a function $f$ that takes an n-tuple of boolean values $x \in \{0,1\}^n$ as input and produces a boolean value $f(x)\in \{0,1\}$ as output. We say that a boolean function $f$ ... of symmetric boolean functions on $n$ variables? $n+1$ $n!$ $\displaystyle \sum^n_{i=0} \begin{pmatrix} n\\i \end{pmatrix}$ $2^{n+1}$
asked Jan 28 in Others soujanyareddy13 27 views
...