Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 3 down vote accepted

NFAe=NFA=DFA=Reg.exp, LR(1)-Grammar=DPDA, CFG=PDA, TM=NTM=TM+

Seems OK to me.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.