The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
83 views

https://gateoverflow.in/?qa=blob&qa_blobid=5516250407315106757

My question is how these two are different...according to my both will generate (a+b)*

asked in Theory of Computation by (117 points) | 83 views
0
i think you are correct both look same to me too..
0

The second string is ((a+b)3)* which can be expanded as ((a+b)(a+b)(a+b))*=((aa+ab+ba+bb)(a+b))* =(aaa+aab+aba+abb+baa+bab+bba+bbb)*

Can this generate any string of length 1 or 2?

0
((a+b)^3)* will generate always string of multiple of 3 in length....by taking this as empty you can generate length 0,1,2 from this (epsilon+(a+b)+(a+b)^2)
+1
According to me actually first one is not MOD machine...because there is no remainder left (0 1 2 all get accepted)..so basically in this case all state are Final state and get optimize to single final state as accepting all (a+b)*....am i right?
0
yes, ROHIT

those two regular expressions are equal and your explanation is obviously right.
0
so thats only the qsn naa length of string mod3 <=2,in this every string in(a+b)* get accepted because doing mod 3 on any length string will give 0,1,2 only so (a+b)*..

in second you are doing the same only
0
Thank you all
+1

L= [(a+b)3]* is language genrating strings multiple of 3. not mod 3.

Ok p= (a+b)3 , now [p3]* will not generate string with length 1,2.

0
Thank you Prashant Sir

Please log in or register to answer this question.



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

39,755 questions
46,768 answers
140,674 comments
58,553 users