The Gateway to Computer Science Excellence

0 votes

IT IS 1 STATE

**I did by drawing ϵ-NFA and then converting it to nfa by ****ϵ closure rule ,my resulting nfa comprised of only one state.Bt even without all these we can see if there is one loop of 1 over the initial state which would be our final state even we can satisfy our regular expression.**

**But i am not confident.if i am wrong plz someone rectify me.**** **

0

ok i am just trying to go from basics it would be easy for me even,

,at first draw the ϵ nfa .. if that is correct then apply ϵ closure procedure or any other way in any standard books to get ur nfa without ϵ. then you will find out that your resulting nfa is of 1 state and it has even just 1 alphabet acording to question that is 1. so its equivalent minimal dfa would be of 1 states and even your nfa witout ϵ would represent your dfa once you draw it(you can easily recognize it once you draw it eg state q_{n}_{ }with self loop of 1 over itself which is our nfa and even dfa as only one transition for 1).

but plz be careful to draw you ϵ nfa .. it is where we all make mistake .if the mistake is there, your procedure may be going in wrong way and your answer may end up wrong

0 votes

You can Obtain This type of problems by simplifying the given equation

Let us Consider above equation as R=(R1+R2)* so this equation we can convert as some basics forms

R=(R1*+R2*)*

R=(R1+R2*)*

R=(R1*.R2*)*

let us take L=(1+1111)*as L=(R1+R2)*

from R1 we can get min length of strings are=0,1,2,3,4,5,6,...etc(all are multiple of 1)

from R2 we can get min length of string are =0,4,8,12,16 (all are multiple of 4)

by observing above min.length string from R1 you can Implement R2 (because R2 subset of R1 we can consider or GCD(R1,R2) is 1)

so With only R1 you can implement whole Language generated by (R1+R2)*

so the Languages is L=1*

so to construct L we need 1 min no of DFA's

Let us Consider above equation as R=(R1+R2)* so this equation we can convert as some basics forms

R=(R1*+R2*)*

R=(R1+R2*)*

R=(R1*.R2*)*

let us take L=(1+1111)*as L=(R1+R2)*

from R1 we can get min length of strings are=0,1,2,3,4,5,6,...etc(all are multiple of 1)

from R2 we can get min length of string are =0,4,8,12,16 (all are multiple of 4)

by observing above min.length string from R1 you can Implement R2 (because R2 subset of R1 we can consider or GCD(R1,R2) is 1)

so With only R1 you can implement whole Language generated by (R1+R2)*

so the Languages is L=1*

so to construct L we need 1 min no of DFA's

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,397 answers

198,611 comments

105,456 users