Member Avatar for kelvinco

how can i convert these to Finite automata

this is the regular expression
(101+111+100)*(0+1)*(0+1)(00+101+11)(10+01)*

pls help me solved this problem:(

  • 2 Contributors
  • 2 Replies
  • 57 Views
  • 15 Hours Discussion Span
  • Latest Post Latest Post by kelvinco

Dani AI

Generated

Good call on checking a book, . Below is a concise, do-it-by-hand plan that addresses the parts found tricky and keeps the work local instead of expanding everything at once.

Break the expression into small pieces: single symbols (0, 1), short fixed words, alternations, concatenation and Kleene stars. Use Thompson-style construction: make tiny NFAs for each atom; implement alternation by a new start with epsilon branches to each alternative; implement concatenation by connecting the accept of the left NFA to the start of the right with an epsilon; implement Kleene star by adding a new start/accept with epsilon loops. After assembling the full NFA compute epsilon-closures and run the subset (powerset) construction to get a DFA; only then minimize and remove unreachable states.

For the final (10+01)* piece it helps to use a small DFA gadget instead of expanding alternations. One compact gadget: start/accept q0; q0 on 1 -> q1, and q1 on 0 -> q0; q0 on 0 -> q2, and q2 on 1 -> q0. From q1 on 1 and from q2 on 0 go to a dead state qd (those are mid-block invalid inputs). Hook q0 of this gadget to the previous part when concatenating; the gadget accepts the empty string and any concatenation of 10 and 01 blocks.

Practical tips: draw the NFA with epsilon labels, test boundary strings (accepted: epsilon, 10, 01, 1010, 1001, 0110; rejected: 1, 0, 11, 00, 101), and minimize only after the DFA is verified correct.

Recommended Answers

All 2 Replies

Member Avatar for sarehu

Do you have a textbook on the subject? Look in that.

If you don't, then imagine interpreting the regular expression by hand. It's not hard to figure out how it maps to a finite automaton that way, if you understand how regular expressions work.

Member Avatar for kelvinco

how can i convert these to Finite automata

this is the regular expression
(101+111+100)*(0+1)*(0+1)(00+101+11)(10+01)*

pls help me solved this problem


>>>> ofcourse i got a book..
the book ofcourse only tell the basic and this problem is realy making my head ache..
i really need someone to just give me the finite automaton of this..
i almost got this FA but expresion on th e last part (10+01)* really fuck of...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.