Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. – Raphael May 22 at 11:37
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|cite|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.