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.

  • 3
    $\begingroup$ 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. $\endgroup$ – Raphael May 22 '16 at 11:35
  • 1
    $\begingroup$ 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.) $\endgroup$ – Raphael May 22 '16 at 11:35
  • 1
    $\begingroup$ Closely related question (thanks, Peter Leupold!). Community votes, please: duplicate? $\endgroup$ – Raphael May 22 '16 at 11:37
  • $\begingroup$ "that does not fit into the ordering" -- the problem is ill-posed; nowhere do they demand a total ordering. $\endgroup$ – 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).

| cite | improve this answer | |
  • $\begingroup$ thanks for the answer, yes Ive looked at that question and because of the difference of my question I thought I needed to put it up here too incase people were interested in another form of the same question. I would however really appreciate if you could expand why LR(0) does not fit into the ordering? I didnt quiet grasp your answer. Thanks alot anyway! $\endgroup$ – Ludvig W May 22 '16 at 7:02
  • $\begingroup$ Your odering is either: LR(0) < DCFL=LR(1) < .... or DFA=RegExp=NFA < DCFL.... So either LR(0) or all the FA and RegExp must stay out of the ordering. Since you must fit all but one into the ordering, only the second hierarchy answers the question. $\endgroup$ – Peter Leupold May 22 '16 at 7:17
  • $\begingroup$ Do you mind explain why? $\endgroup$ – Ludvig W May 22 '16 at 9:42
  • 3
    $\begingroup$ @Lurr You should really do your own homework... $\endgroup$ – Raphael May 22 '16 at 11:36
  • $\begingroup$ @Lurr, you might want to take a look at our advice on how to ask a good question. Also, to share some general advice: 1) spend at least an hour on the problem on your own, before asking, 2) use all material available, including checking Wikipedia and textbooks, 3) talk to fellow students about the problem before asking if possible, then 4) ask about a specific aspect of your approach (don't just ask us to solve the problem), and 5) be sure to show us in the question what approaches you've tried on your own, and what progress you made. $\endgroup$ – D.W. May 23 '16 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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