LR(0) expressive power

Question

So I have grouped the following formalisms into a power hierarchy (and made classes for them):

Class 1

• DFA
• NFA
• NFAϵ
• reg.exp

Class 2 (DCFL expressivity?)

• LR(1)
• DPDA

Class 3

• CFG
• PDA

Class 4

• TM
• NTM

Class 4 is the most powerful class and Class 1 is the least powerful. Now I want to compare them to LR(0) parsers. My current intuition is that LR(0) parsers can handle all of Class 1 (and probably belongs to class 1). Class 2 has more power than LR(0) due to the fact that LR(0) defines a subset of Class 2 (DCFL's with the prefix property).

So I guess the question is, should LR(0) parsers be put into its own class or should it go into Class 1 (which would be my guess).

Answer 1

You're correct that all regular languages have a LR(0) grammar. Moreover, there are LR(0) grammars which generate a non-regular language. (Exercise: Construct a LR(0) grammar for $\{ a^n b^n\,|\,n>0 \}$.)

LR-ness is a tricky concept to get a grasp on, because LR-ness is a property of the grammar, not necessarily the language. Having said that, it is known that all DCFLs can be recognised by a LR(k) parser in $O(n)$ time. It's also known that any LR(k) grammar can be mechanically transformed into an equivalent LR(1) grammar, and that there are examples for which there is no LR(0) grammar. So LR(1) is the same as DCFL/DPDA, and LR(0) is a proper subset.

So, yes, DCFL/DPDA/LR(1) sits somewhere between 3 and 4 on the Chomsky hierarchy, and LR(0) sits between that and 4. (By the way, don't forget Chomsky type 2 when you're examining hierarchies of languages and machines.)