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