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.