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"
pdf
owner:
miller - (no access) - Michael Sipser-Introduction to the Theory of Computation-Course Technology (2012).pdf, p131
Summary
status | not read | | reprioritisations | |
---|
last reprioritisation on | | | suggested re-reading day | |
---|
started reading on | | | finished reading on | |
---|
Details