What does it mean to say a language is context-free?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ See en.wikipedia.org/wiki/Context-free_language $\endgroup$– FixeeApr 10, 2011 at 4:10
-
17$\begingroup$ I did not quite understand the wikipedia, which was why I posted a question here, hoping someone could explain it in laymans terms. $\endgroup$– user9377Apr 10, 2011 at 4:15
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
Given the technical definition of what a language is and what context-free is, it means that in the processing of rules defining the language, no context is used. That is, any variable is rewritten by itself, with no context. Once a variable is produced in a derivation, none of the string around that variable will ever be involved in any further derivation...no context is used in rewriting a variable.
More complicated languages do not have this restriction (they may allow use of context/other adjacent variables and terminals in rewriting a variable).
Context-free languages are "easier" to parse (quicker/more efficiently) than context sensitive ones.
Note that the term 'context' is very technical here; it is referring to the context of a substring when rewriting. Technical terms have a life of their own and don't necessarily relate well to the first layman's understanding of the word.
-
$\begingroup$ Sorry you did not provide any example what you mean by context. $\endgroup$– zak100Nov 24, 2019 at 15:31
-
1$\begingroup$ @zak100 'context' is the parts of the string on either side of the variable. A context free grammar only has rules of the form A -> BC. One that uses context might be xAy -> BC. The 'x' and 'y' are considered context. $\endgroup$– MitchNov 24, 2019 at 16:10
$\begingroup$
$\endgroup$
0
A context-free grammar is defined as a grammar in which every production rule is of the form $A \rightarrow \alpha$, where $A$ is a variable and $\alpha$ is a sequence of variables and terminals.
Formally, a context-free grammar can be defined as a 4-tuple $(V, \Sigma, R, S)$, where $V$ is a finite set consisting of the variables, $\Sigma$ is a finite set consisting of the terminals, $R$ is a set of production rules (in the form mentioned above), and $S \in V$ is the starting variable.
The language of a context-free grammar is the set of strings that can be derived from its start variable. A context-free language is any language that is generated by a context-free grammar.
For example, $\{ 0^n1^n : n \ge 0 \}$ is context-free because it is generated by the context-free grammar $(\{S\}, \{0, 1\}, R, S)$, where the set of rules, $R$, is $$S \rightarrow 0S1 \mid \varepsilon.$$
(Note: I am using $\varepsilon$ to denote the empty or null string.)
As seen in this example, the set of context-free languages contains languages that are not regular. Also, since it is easy to mimic a DFA with a context-free grammar, the set of regular languages is a proper subset of the set of context-free languages. Pushdown automata are the automata cousins of context-free grammars; they accept context-free languages and there exist algorithms to convert between the two models.
Note that the language $\{ a^nb^nc^n : n \ge 0 \}$ is not context-free (try to write a context-free grammar to generate this language and you will get a feeling for why). It can be proven that the language is not context-free with the pumping-lemma for context-free languages, which I will leave as an exercise for the reader.
There are more powerful grammars, such as context-sensitive grammars, which allow the production rules to have the form $\beta A \gamma \rightarrow \beta\alpha\gamma$, where $\alpha$, $\beta$, and $\gamma$ are sequences of variables and terminals. Context-sensitive grammars are as powerful as linear bounded automata (LBA).
$\begingroup$
$\endgroup$
2
Another characterisation is this: The set of context-free languages CFL is the set of all languages that are accepted by (maybe nondeterministic) push-down automata (finite automata plus one stack).
More intuitively, context-free languages have the property that different parts of a word are independent in a certain sense, namely in the same way as dynamic programming optimises subproblems independently. Not conincidentally, context-free grammars can by parsed by dynamic programming (CYK algorithm), non-context-free can not (in general).
-
$\begingroup$ It might be a good idea to explicitly state that you are referring to non-deterministic PDAs. $\endgroup$ Apr 10, 2011 at 15:10
-
1$\begingroup$ Agreed, thanks. I "grew up" with PDA $=$ NPDA $\cup$ DPDA with NPDA $\cap$ DPDA $= \emptyset$. DPDA $\subset$ NPDA = PDA is also common. $\endgroup$– RaphaelApr 10, 2011 at 15:40
$\begingroup$
$\endgroup$
3
My understanding is that a language is context-free if all statements can be understood without requiring external context, which is true for no natural language and those aspects of programming languages that do not rely on data or APIs from external sources.
-
3$\begingroup$ Most programming languages are not context-free. What PL people call "static semantics" or "context restrictions" (often even subsumed in the notion of "syntax") are certain computable criteria (type correctness, visibility, ...) that require more computational power. It is, however, true that pure syntax of programming languages is usually context-free, i.e. given by a CFG. Not all "valid" programs in that regard are accepted by the compiler, obviously. $\endgroup$– RaphaelApr 10, 2011 at 10:29
-
$\begingroup$ I think I misunderestimated the prevalence of data and APIs external to the environment. $\endgroup$ Apr 10, 2011 at 11:30
-
$\begingroup$ Maybe, but that is not the point. Even assuming you have access to all code while compiling, you have certain problems. Very simple example: forward references (e.g. methods in a Java class) can not be resolved/checked in one pass, i.e. not by a PDA. Name resolution is problematic in general, since a PDA has no way to store arbitrarily many (valid) identifiers with random access. $\endgroup$– RaphaelApr 10, 2011 at 12:21