[Solved]: Formal Languages – Expressive power of Formalisms

Problem Detail: 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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7682