retagged by
447 views
0 votes
0 votes

retagged by

2 Answers

1 votes
1 votes

(a) L = $\left \{ a^{n}b^{n} : n \geq1 \right \}\cup \left\{a^{n}b^{m}: n \geq1,m\geq 1 \right \}$

       L can also be written as $\left\{a^{n}b^{m}: n \geq1,m\geq 1 \right \}$ as $\left \{ a^{n}b^{n} : n \geq1 \right \}$ is already included in $\left\{a^{n}b^{m}: n \geq1,m\geq 1 \right \}$

       L is regular because Regular expression for L is $a^{+}b^{+}$

(b) L = $\left \{ a^{n}b^{n} : n \geq1 \right \}\cup \left\{a^{n}b^{n+2}: n \geq1\right \}$

     L = $\left \{ a^{n}b^{n}(\lambda+bb) : n \geq1 \right \}$

     Assuming L is a regular language. Let p be the pumping length given by the pumping lemma.

     We pick our string , w = $a^{p}b^{p}(\lambda+bb) $, and $\left | w \right | > p$

     $w_{i} = xy^{i}z$ , i = 0,1,2,3...

     y must contain entirely of a's 

     suppose $\left | y \right | = k$

     then when i = 3, $xy^{3}z = a^{p+3k}b^p(\lambda+bb)$

     This shows that $n_{a} > n_{b} $ but no such string exists in L 

     This indicates that the assumption that L is regular must be false. 

     Hence L is not regular

0 votes
0 votes
a) L={$a^{+}b^{+}$} regular expression$\Rightarrow FA$

b) L={${\color{Red} a^{n}b^{n}}(\epsilon +aa)$} comparision between a and b$\Rightarrow CFL$

Related questions

0 votes
0 votes
0 answers
1