Given a word and a context-free grammar , how do we determine if ?
One way is to look for any subword of such that there is a production . If this is successful, we may replace with in to obtain a word , so that . We may then repeat the process on to obtain another word such that (if successful). In the end, if everything works successfully, we arrive at the starting non-terminal symbol , and get a derivation as a result, so that . This procedure is known as the bottom-up parsing of the word .
In general, unless one is very lucky, successfully finding a derivation requires many trials and errors, since at each stage, for a given word , there may be several words such that .
Nevertheless, there is a particular family of context-free grammars, called the grammars, which make the bottom-up parsing described above straightforward in the sense that, given a word , once a word is found such that , any other word such that forces . Here, is known as the rightmost derivation (meaning that is obtained from by replacing the rightmost non-terminal in ). The in means scanning the symbols of from left to right, stands for finding a rightmost derivation for , and means having the allowance to look at up to symbols ahead while scanning.
The details are as follows:
Definition. Let be a context-free grammar such that is not a production of , and an integer. Suppose is any sentential form over with the following setup: where
is a terminal word,
a production, and
Let , and the prefix of of length (if , then set ).
Then is said to be if is another sentential form having as a prefix, with the following setup: , where
is a terminal,
is a production, and
Simply put, if and are the rightmost derivations of and respectively, and if the prefix of obtained by including symbols beyond the last replacement in is also a prefix of , then the prefix of obtained by including symbols beyond the last replacement in is also a prefix of , where and are words at the next to the last step in and respectively. In particular, if , then . This implies that any derivable in an grammar has a unique rightmost derivation, hence
Any grammar is unambiguous.
Let be the grammar consisting of one non-terminal symbol (which is also the final non-terminal symbol), two terminal symbols , with productions
Then is not for any . For instance, look at the following two derivations of :
Here, , . Let . Then the criteria in the definition are satisfied. Yet, . Therefore, is not .
Note that the grammar above generates the language , which can also be generated by the grammar with three non-terminal symbols , with the final non-terminal symbol, where the productions are given by
However, this grammar is .
Determining whether a context-free grammar is is a non-trivial problem. Nevertheless, an algorithm exists for determining, given a context-free grammar and a non-negative integer , whether is . On the other hand, without specifying in advance, no algorithms exist that determine if is for some .
Definition. A language is said to be if it can be generated by an grammar.
Every language is deterministic context-free. Every deterministic context-free language is .
Hence, deterministic context-free languages are the same as languages.
|Date of creation||2013-03-22 19:00:31|
|Last modified on||2013-03-22 19:00:31|
|Last modified by||CWoo (3771)|