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

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

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

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?

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

those two regular expressions are equal and your explanation is obviously right.
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
Thank you all

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.

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

36,995 questions
44,571 answers
43,637 users