I wonder how do you clasify S->a (where a is a Terminal Symbol)

It can be right linear,left linear and context free at the same time?

So the only way to distinguish them is to see what productions there are with Non-terminal symbols (like S in this example)

0) If I see S->a it can be (left/right/context-free) impossible to know

1) If I see only production in the form of S->a and S-> aS then it is right lineair

2) If I see only production in the form of S->a and S-> Sa then it is left lineair

3) If I see a mix (left and right) of the form of S-> aS and S-> Sa then I know that it is context free

4) If I see a production with a terminal symbol on the left AND on the right then I also know it is context free : like this S->aSa

Are these 5 statements correct? Am I missing scenario's to define the difference between regular and context free?


1 Answer 1


Your statement is correct. However your cases do not cover the full width of context-free grammars. All your examples are linear grammars.

In general one also allows right-hand sides that contain more than one non-terminal, like A->BC.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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