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.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,755 questions

46,768 answers

140,674 comments

58,553 users