# Order classic notions of computability by power

I need some help with a question. I'm currently studying for an exam and I could therefore use some help with this following question:

Order the following formalisms (but one) 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. Point out the formalism that does not fit into the ordering.

• Context Free Grammars ( CFG )
• Deterministic Finite Automata (DFA)
• Deterministic Pushdown Automata (DPDA)
• LR(0) grammars
• LR(1) grammars
• Nondeterministic Finite Automata ( NFA)
• Nondeterministic Finite Automata with epsilon-transitions ( NFA - epsilon)
• Nondeterministic Turing Machines ( NTM )
• Pushdown Automata ( PDA )
• Regular Expressions ( reg. exp )
• Turing Machines ( TM )
• Turing Machines with two heads ( TM 2h )

The trick here is to find the one that does not fit into the ordering and why. I'm just not able to find that one.

• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael May 22 '16 at 11:35
• Hint: collect the corresponding theorems from your lecture notes. The only ones you may not see in an introductory course on automata/computability are LR(0/1). (Heck, even Wikipedia has all the information you need.) – Raphael May 22 '16 at 11:35
• Closely related question (thanks, Peter Leupold!). Community votes, please: duplicate? – Raphael May 22 '16 at 11:37
• "that does not fit into the ordering" -- the problem is ill-posed; nowhere do they demand a total ordering. – Raphael May 22 '16 at 11:39

I think that LR(0) is incomparable to the regular languages, see the answers to question Are regular expressions $LR(k)$? . Thus it does not fit in a linear hierarchy with all the rest. It could be the bottom element, but for REG there are several characterizations; thus more than one class would not fit in the hierarchy. Therefore they probably mean LR(0).