1
$\begingroup$

I was following a discussion on a website, where a fellow scholar claims that this grammar

S→ aAa | bAb | ϵ

A→aA | bA |ϵ

is not CSG, so it should also NOT be a CFG. But this grammar properly satisfies the rules of CFG according me, on the other hand it fails to satisfy the conditions of CSG, which states that--

In addition, a rule of the form

S → λ

where λ represents the empty string and S does not appear on the right-hand side of any rule is permitted

So the given grammar is definitely not in CSG. But According to chomsky hierarchy

enter image description here

A CFG should be contained in CSG, so why this rule is NOT being satisfied for this case?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Note that the Chomsky Hierarchy is nowsadays considered as a hierarchy of language families. For each of the levels we both have suitable grammars and automata to generate and accept the languages in the family. Usually there is a relation between the devices for the different levels, but in some cases we have to be careful about the details.

You are right. The given grammar is context-free, but it is not context-sensitive. The reason is that with CSG we have to restrict the possibility for variables to generate the empty string. Technically the reason for this is that the context-sensitive languages are not closed uner erasing (deleting some letters).

So, any CFG that does not have $\varepsilon$-rules is also a CSG. Usually a CSG is not allowed to have $\epsilon$-rules. Of course that would mean that CSL do not contain the empty string. Well, the empty string can be handles separately if we need it. The same is true for, say, CFG in Chomsky normal form. Strict ChNF does not allow the empty string, but that is not a real restriction. Either we deal with the language without $\varepsilon$, or we have some complicated formulation that will allow generating $\varepsilon$ only in the first step of the derivation.

Improve this answer
$\endgroup$
3
  • $\begingroup$ ok, so "every cfg is not a csg". I get it, but is this statement--> "for every CFG there must be a CSG" true? that is if a cfg is not even in csg we can convert it into one in all the cases? $\endgroup$
    – Turing101
    Commented Sep 1, 2019 at 17:29
  • 1
    $\begingroup$ Every context-free language is also a context-sensitive language. So indeed, the statement for every CFG there is an equivalent CSG. For the CFG this is even easy as for every context-free grammar we can find an equivalent CFG without $\varepsilon$-rules. Without those rules, the CFG is itself a CSG. Again, as in my answer, we have to be careful and consider how we generate the empty string. If we care at all.) $\endgroup$
    – Hendrik Jan
    Commented Sep 1, 2019 at 18:16
  • $\begingroup$ Ok...thank u.. :) $\endgroup$
    – Turing101
    Commented Sep 2, 2019 at 4:03
0
$\begingroup$

A CFG (in the strict sense) can't have a right hand side $\epsilon$ in a production. Neither can a CSG. So your example is neither, it is an unrestricted grammar.

You can allow "CFGs" with $\epsilon$ on right hand side of productions, because they can be modified automatically to eliminate those right hand sides. It is allowed in e.g. parser generators and in programming language descriptions, as it provides a very useful (and easily understandable!) shorthand. So, in C you can say "a function body is declarations, definitions, and statements in braces", and each of the above can be empty. If not, you'd have to lay out the full eight alternatives with missing pieces. Not at all nice.

Improve this answer
$\endgroup$

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.