Wikipedia:

context-free language


A context-free language is a formal language that can be defined by a context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.

Examples

An archetypical context-free language is L = \{a^nb^n:n\geq1\}, the language of all non-empty even-length strings, the entire first halves of which are a's, and the entire second halves of which are b's. L is generated by the grammar S\to aSb ~|~ ab, and is accepted by the pushdown automaton M = ({q0,q1,qf},{a,b},{a,z},δ,q0,{qf}) where δ is defined as follows:

δ(q0,a,z) = (q0,a)
δ(q0,a,a) = (q0,a)
δ(q0,b,a) = (q1,x)
δ(q1,b,a) = (q1,x)
δ(q1,b,z) = (qf,z)
where z is inital stack symbol and x means pop action.

Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar S\to SS ~|~ (S) ~|~ \lambda. Also, most arithmetic expressions are generated by context-free grammars.

Closure Properties

Context-free languages are closed under the following operations. That is, if L and P are context-free languages and D is a regular language, the following languages are context-free as well:

Context-free languages are not closed under complement, intersection, or difference.

Nonclosure under intersection

The context-free languages are not closed under intersection. Proving this is given as an exercise in Sipser 97. It can be seen by taking the languages A = \{a^m b^n c^n \mid m, n \geq 0 \} and B = \{a^n b^n c^m \mid m,n \geq 0\}, which are both context-free. Their intersection is A \cap B = \{ a^n b^n c^n \mid n \geq 0\}, which can be shown to be non-context-free by the pumping lemma for context-free languages.

Decidability properties

The following problems for context-free languages are undecidable:

The following problems are decidable for context-free languages:

  • is L(A)=\emptyset ?
  • is L(A) finite?
  • Membership: given any word w, does w \in L(A) ? (membership problem is even polynomially decidable - see CYK algorithm)

Properties of context-free languages


References

  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Chapter 2: Context-Free Languages, pp.91–122.


Automata theory: formal languages and formal grammars
Chomsky
hierarchy
Grammars Languages Minimal
automaton
Type-0 Unrestricted Recursively enumerable Turing machine
n/a (no common name) Recursive Decider
Type-1 Context-sensitive Context-sensitive Linear-bounded
n/a Indexed Indexed Nested stack
n/a Tree-adjoining Mildly context-sensitive Embedded pushdown
Type-2 Context-free Context-free Nondeterministic pushdown
n/a Deterministic context-free Deterministic context-free Deterministic pushdown
Type-3 Regular Regular Finite
Each category of languages or grammars is a proper subset of the category directly above it.

 
 
 

Join the WikiAnswers Q&A community. Post a question or answer questions about "context-free language" at WikiAnswers.

 

Copyrights:

Wikipedia. This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Context-free language" Read more

Search for answers directly from your browser with the FREE Answers.com Toolbar!  
Click here to download now. 

Get Answers your way! Check out all our free tools and products.

On this page:   E-mail   print Print  Link  

 

Keep Reading

Mentioned In: