The Gateway to Computer Science Excellence
+7 votes
400 views

in Theory of Computation by (265 points) | 400 views

3 Answers

+8 votes
Best answer

$1.L_{1}=0^{*}10^{*}10^{*}$


$2.L_{2}=aaaa^{*}\left ( bb \right )^{*}$


$3.L_{3}=\left ( 0+1 \right )^{*}00\left ( 0+1 \right )^{*}+\left ( 0+1 \right )^{*}11\left ( 0+1 \right )^{*}$


$4.L_{4}=b^{*}(ab^{*}ab^{*}ab^{*})^{*}$

by Boss (16k points)
edited by
+1
For $L_4$, b is not accepted.
0
sir $L_{4}=(b^{*}ab^{*}ab^{*}ab^{*})^{+}?$
0

can we write L1 as (110* + 0*110*+ 0*10*1+10*10*) ? 

I know L1=0*10*10*  covers it , but still is above is also correct?

0
No, that also won't accept b rt? We should allow no a's because 0 is divisible by 3.
0
Sir , i am not getting you .

If you are saying that my $L_{4}$ should accept $b$,then my $L_{4}$ is actually accepting $b$

$L_{4}=b^{1}(b^{*}ab^{*}ab^{*}ab^{*})^{0}b^{0}$

 

Actually i too though that $n(a)=0$ should be accpeted as 0 is divisible by 3
0
yes, sorry I missed that. But you can avoid b* at end.
0
okk sir , thank you :)
0
thank you Sir
0
for L4 why not   b*(ab*ab*ab*)*   ?
0
@diksha , yes you are correct.Thanks
0

L4 can also be expressed as (b + ab*ab*a)*

+1 vote
solution

Ans1.   0*10*10*
by (129 points)
0 votes

.........

by Boss (35.4k points)
edited by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,651 questions
56,214 answers
194,173 comments
95,423 users