i think you are correct both look same to me too..

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

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

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

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

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

in second you are doing the same only

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 568
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

48,450 questions

52,747 answers

183,347 comments

68,220 users