CFL (Context free language)
CFLs are used by the compiler in the parsing phase as they define the syntax of a programming language and are used in many editors.
There are four important components in a grammatical description of a language:
- There is a set of symbols that form the strings of the language being defined. They are called terminal symbols, represented by V t .
- There is a finite set of variables, called non-terminals. These are represented by V n .
- One of the variable represents the language being defined; it is called the start symbol. It is represented by S.
- There are finite set of rules called productions that represent the recursive definition of a language. Each production consists of:
● A variable that is being defined by the production. This variable is often called the head of the production.
● The production symbol ->.
● A string of zero or more terminals and variable.
Non - CFL (Non -Context free language)
Not all languages are CFL. Non-CFL is the name of languages that are not Context-Free.
The analysis of the word production machine from grammar is required to prove the point that all languages are not meaning - free.
live production: A live production is called a production of the nonterminal form * strings of two non-terminals.
dead production: A development of the non-terminal * terminal form is referred to as a dead production.
It should be noted that all CFGs in the CNF only have these types of output. The theorem below is
Theorem: if a CFG is in CNF and if there is a constraint on the use of live output at most once each, then it is only possible to produce finite words.
It must be noted that it increases the number of nonterminals by one each time a live output is applied during the derivation of a name.
Similarly, the application of dead manufacturing reduces the nonterminals by one. Which indicates that one more dead production is applied to produce a word than live productions e.g.
One live and two dead productions are presented here.
In general, if a CFG has p live and q dead productions in CNF, then at most (p+1) letters are all words produced without repeating any live output.
Key takeaway:
- CFLs are used by the compiler in the parsing phase as they define the syntax of a programming language and are used in many editors.
- Not all languages are CFL. Non-CFL is the name of languages that are not Context-Free.
Lemma: The language L = {anbncn | n>=1} is not context free.
Proof (By contradiction)
Assuming that this language is context-free; hence it will have a context-free
grammar.
Let K be the constant of the Pumping Lemma.
Provided the aKbKcK series, where L is greater than K in duration.
By the Pumping Lemma this is represented as uvxyz, such that all uvixyiz are also in, which is not possible, as: either v or y cannot contain many letters from {a,b,c} ; else they are in the wrong order .
if v or y consists of ‘a’s, ‘b’s or ‘c’s, then uv2xy2z cannot maintain the balance amongst the three letters.
Lemma: The language L = {aibjck | i < j and i < k} is not context free.
Proof (By contradiction)
Assuming that this language is context-free; hence it will have a context-free grammar.
Let K be the Pumping Lemma constant.
Considering the string aKbK+1cK+1, which is L > K.
By the Pumping Lemma this must be represented as uvxyz, such that all uvixyiz are also in L.
-As mentioned previously neither v nor y may contain a mixture of symbols.
-Suppose consists of ‘a’s.
Then there is no way y cannot have ‘b’s and ‘c’s. It generates enough letters to keep
them more than that of the ‘a’s (it can do it for one or the other of them, not both)
Similarly, y cannot consist of just ‘a’s.
So, suppose then that v or y contains only ‘b’s or only ‘c’s.
Consider the uv0xy0z string that must be in L. Since both v and y have been dropped, we must have at least one 'b' or one 'c' less than we had in uvxyz, which
It was akbk+1ck+1. Consequently, to be a member of L, this string no longer has enough of either 'b's or' c's.
● Intersection − If A1 and A2 are context free languages, then A1 ∩ A2 is not necessarily context free.
● Intersection with Regular Language − If A1 is a regular language and A2 is a context free language, then A1 ∩ A2 is a context free language.
● Complement − If A1 is a context free language, then A1’ may not be context free.
- John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Education Asia.
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.
- John Martin, Introduction to Languages and the Theory of Computation, Tata McGraw Hill.
