Question

Let $l,m,n$ be 3 regular expressions. Consider the following identities.
$I.(l^{\ast }{m}^{\ast }{n}^{\ast }{)}^{\ast }=(l{m}^{\ast }+m{n}^{\ast }+n{l}^{\ast }{)}^{\ast }II.(mn+m{)}^{\ast }m=m(nm+m{)}^{\ast }III.(l^{\ast }{m}^{\ast }{n}^{\ast }{)}^{\ast }=(l^{\ast }+m^{\ast }n+n^{\ast }{)}^{\ast }IV.(l^{\ast }m{)}^{\ast }=(l+m{)}^{\ast }$

How many of the above identities are incorrect._________.

Answer 1

$\text{Correct: I, II}\text{Incorrect: III, IV}\text{I is classical case of bracketed star.}\begin{array}{cc}\text{LHS}& =(l+m+n{)}^{\ast }\\ \text{RHS}& =(l+m+n+\cdots \cdots {)}^{\ast }\\ \text{Since we can get}l,m,n\text{separately, RHS is equal to}(l+m+n{)}^{\ast }& \\ \text{Therefore I is true.}& \\ \text{II is also true. Let's see why}& \\ (mn+m{)}^{\ast }& =m(mn+m{)}^8\\ \text{LHS:}& =(mn+m{)}^{\ast }m\\ & =(m+mn{)}^{\ast }\text{(Commutative property of regular expressions)}\\ & =\left(\frac{m}{p}\frac{(\in +n)}{q}\right)\frac{m}{q}\\ \text{Now using,}(pq{)}^{\ast }p& =p(qp{)}^{\ast },\text{we get}\\ & =m\left[\right(\in +n)m{]}^{\ast }\\ & =m[m+nm{]}^{\ast }=RHS\Rightarrow \text{II is true}\end{array}\text{III is false as we can't get}"m"\text{separately form RHS.}\text{Similarly, IV is also false as we can't generate}"l"\text{separately form LHS.}\text{Therefore (2) is the answer.}$