- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

A context-free grammar (CFG) consisting of a finite set of grammar rules is a quadruple **(V, T, P, S)**

Where,

V is a variable (non terminals).

T is a set of terminals.

P is a set of rules, P: V→ (V ∪ T)*, i.e., the left-hand sides of the production rule. P does have any right context or left context.

S is the start symbol.

By using the rules of any language, we can derive any strings in that language.

For language a* CFG is as follows −

S -> aS

S -> ɛ

Here,

S are the variables.

a and ɛ terminals.

S is the start symbol.

By using these rules, we can derive any number of a's.

For Example, consider string aaaaa as CFG as shown below −

S aS rule 1 aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaɛ rule 2 aaaaa

Context free language is created by context free grammar and it includes regular languages.

The same context free languages can be generated by multiple context free grammars.

**Example 1**

Example of language that is not regular but it is context free is **{ anbn | n >= 0 }**

The above example is of all strings that have equal number of a's and b's and the notation a3b3 can be expanded out to aaabbb, where there are three a's and three b's.

The pumping Lemma provides the ability to perform negative test. If the language does not satisfy the pumping lemma, then it can be said that it is not context free. Pumping lemma is mathematical proof which takes time to apply it on context free languages.

**Example 2**

Consider another example of context free that is not regular.

S -> aSb | ɛ

This example is not regular because we cannot express it with a finite state machine or regular expression. We should be able to count the number of A's and check that number of B's matches. Moreover, it cannot be done with finite state as n could be anything.

- Related Questions & Answers
- What are the closure properties for context free language?
- Explain the context free language closure under concatenation?
- Explain Pumping lemma for context free language
- How to generate the language for context free grammar?
- Explain the context free language closure under union operation?
- What is context free grammar? Explain with examples
- Explain about pumping lemma for context free language?
- Generate a Context-free grammar for the language L = {anbm| m≠n}?
- Explain the simplification of context free grammar in TOC
- What are the situations that give you goosebumps?
- Convert the given Context free grammar to CNF
- Give examples for the percentage of completion method
- Generate a CNF for a given context free grammar
- What are some basic examples of Python Regular Expressions?
- Explain the Star Height of Regular Expression and Regular Language

Advertisements