I need help with the following question:
Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state which, if any, of them are equivalent.
• Turing Machines (TM) • Regular expressions (reg.exp.) • Turing Machines with multiple tapes (TM+) • Pushdown Automata (PDA) • Nondeterministic Finite Automata with ǫ-transitions (NFAǫ) • Nondeterministic Finite Automata (NFA) • LR(1) grammars • Nondeterministic Turing Machines (NTM) • Deterministic Pushdown Automata (DPDA) • Deterministic Finite Automata (DFA) • Context-free Grammars (CFG)
Is this the correct answer ? I have a exam next week and need to know If my answer is correct.
NFAe=NFA=DFA=Reg.exp, LR(1)-Grammar=DPDA, CFG=PDA, TM=NTM=TM+
Thanks in advance
Asked By : mrjasmin
Answered By : Hendrik Jan
NFAe=NFA=DFA=Reg.exp, LR(1)-Grammar=DPDA, CFG=PDA, TM=NTM=TM+
Seems OK to me.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7682
0 comments:
Post a Comment
Let us know your responses and feedback