Revision #229 → #1429 · back to history
addedDeterministic finite automaton (DFA)7a089d0ac67d
addedNondeterministic finite automaton (NFA)da2e47654484
addedEvery DFA is an NFA7050ce3c8a8b
addedSubset construction yields equivalent DFA1ac950ae990d
addedNFAs recognize only regular languagesadcb225d73c9
addedNFA as a 5-tuple9b7beebd4b0c
addedRecognized language of an NFA9cdac541d5da
addedAcceptance via state sequence0df4f5c537f2
addedAcceptance via recursive reachable-set definition4a9d732c18ea
addedMultiple initial states reducible to single initial state81ee6200ea6f
addedNFA M accepting strings ending in 1c2b1494b5896
addedDFA is a special kind of NFA1b6624e4ac86
addedEvery NFA has an equivalent DFA (powerset construction)005ceaf738e7
addedExponential state blowup of powerset construction9adf9bcb4af2
addedNFA with ε-moves (NFA-ε)209434518ece
addedNFA-ε as a 5-tupleeab763e41b69
addedε-closure of a statee79bdcb1afd0
addedε-closure of a set of states6b1130a4846b
addedExtended transition function of NFA-ε999cd2f1ad0c
addedAcceptance by an NFA-ε1b362db43370
addedNFA-ε for even number of 0s or 1s9b5311ecd76a
addedEvery NFA-ε has an equivalent NFA1cde713b54f6
addedEquality of extended transition functions by induction81bdcae9aaee
addedNFA-ε is equivalent to DFA1f042a2a73bf
addedNFA-recognized languages closed under operationse9277d5cdddc
addedClosure under union054b2599f776
addedClosure under intersection2f60344432fe
addedClosure under concatenation5462dac6240a
addedClosure under negationfd9b050c6d7f
addedClosure under Kleene closure8147c6ef700c
addedLanguage accepted by an NFA is regular9623a44e7b20
addedEvery NFA has an equivalent DFAdb674afd0f18
addedTime and space bound for NFA simulationa8ad61b9f76a
addedEmptiness problem solvable in linear time981072ffe6d2
addedUniversality of NFA is PSPACE-complete2f0c2dc4bc8a
addedInclusion problem is PSPACE-complete67a8478720b9
addedCounting accepted words is #P-hardb51421bfb0eb
addedNFAs and DFAs are equivalenta5ce2ec5a6d8