2
$\begingroup$

Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ?

The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (Assuming it's not in CNF)

Is my intuition right though?

$\endgroup$
1
$\begingroup$

Your intuition is not fully right. Consider the membership problem which is defined by $$L = \{ \langle G, w\rangle: G \ is \ a\ CFG \ that\ generates \ the\ finite \ word \ w\}$$ It is know that $L$ is decidable and the right way to prove this is by using CNF for CFGs. The problem with what you mentioned is the following. Let $G$ be a CFG and let $w\in \Sigma^*$ be a finite word. If $G$ is not in CNF form, then you propose the following: "systematically check" if there is a derivation for $w$ in $G$. Well, this is not a good idea. Assume that you go over all derivations in some lexical ordering and once you find a derivation for $w$, we stop. The problem with this approach is that we may not halt. As a specific example, consider the following CFG: the rules are $S\to A$, $A\to A|a$ , where:

  • S is the strat variable.

  • A is a variable.

  • a is a letter (or terminal).

Clearly, $L(G) = \{ a\}$. But the algorithm suggested does not halt as you need to try an infinite number of derivations and check whether $\epsilon$ is derived by one of them. Indeed, you can apply the rule $A\to A$ as much as you like.

The nice thing about CNF form is that if a word $w$ is in $L(G)$, then it requires exactly $2|w| - 1$ derivation rules to derive $w$. Hence, in order to check whether $w$ is in $L(G)$, you only need to consider all derivations of length $2|w| -1$. In particular, the algorithm halts.

$\endgroup$
  • $\begingroup$ I see Your point. However how do I determine if $\varepsilon$ belongs to the given grammar in CNF, which by definition does not contain any $\varepsilon$ transformations? Does it mean, that after I'm done with the iteration and did not found the word I was looking for then $\varepsilon$ belongs to $L(G)$? Or does the iteration stops and accepts immediately on input $\varepsilon$? $\endgroup$ – Adrian Mwah Oct 7 '18 at 13:39
  • $\begingroup$ This is not correct, the CNF form can contain the following rule: $S\to \epsilon$ where $S$ is the start variable. However, a variable that is not the start variable cannot derive $\epsilon$. Given this, you simply check whether $S\to \epsilon$ is in your CNF grammar. $\endgroup$ – Bader Abu Radi Oct 7 '18 at 13:42
  • $\begingroup$ See here: en.wikipedia.org/wiki/Chomsky_normal_form $\endgroup$ – Bader Abu Radi Oct 7 '18 at 13:44
1
$\begingroup$

You can transform the CFG to Greibach normal form, and then simply check whether the rule $S\rightarrow \varepsilon$ exists.

In fact, you are asking whether there is a parsing algorithm for CFG.

$\endgroup$
1
$\begingroup$

In a way, yes. But is is not straightforward what means "systematically check".

Probably the best way is to determine all the nullable symbols of the grammar. Here a symbol $X$ is nullable if there exists a derivation $X\Rightarrow^* \varepsilon$. Then check whether axiom $S$ itself is nullable.

Now $X$ is nullable if there exists a production $X\to \varepsilon$ or (recursion) if there exists a production $X\to\alpha$ such that all symbols in $\alpha$ are nullable. I think an algorithm for this repeatedly looks for productions of the type $X\to\alpha$ with $\alpha$ nullable, and marking the found $X$ as nullable. The algorithm stops when after a cycle over all productions no new nullable symbols are found.

If your grammar is in Chomsky or Greibach normal form, then either generating $\varepsilon$ is ignored, or it can only occur at the first step with a special $S\to\varepsilon$ production. First transforming into Chomsky or Greibach normal form does not particularly help, as those transformations include determining the nullable symbols.

$\endgroup$

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.