Do you want BuboFlash to help you learning these things? Or do you want to add or correct something? Click here to log in or create user.

You can convert any DFA into an equivalent CFG as follows. Make a variable R i for each state q i of the DFA. Add the rule R i → aR j to the CFG if δ(q i , a) = q j is a transition in the DFA. Add the rule R i → ε if q i is an acc ept state of the DFA. Make R 0 the start variable of the grammar, where q 0 is the start state of the machine. Verify o n your own that the resulting CFG generates the same language that the DFA recognizes
If you want to change selection, open document below and click on "Move attachment"


owner: miller - (no access) - Michael Sipser-Introduction to the Theory of Computation-Course Technology (2012).pdf, p131


statusnot read reprioritisations
last reprioritisation on suggested re-reading day
started reading on finished reading on



Do you want to join discussion? Click here to log in or create user.