Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Context-Free Grammar(CFG)
2.1.
Explanation
2.2.
Examples
3.
Application, Properties, and Types of Grammar
3.1.
Applications
3.2.
Properties
3.3.
Ambiguity in CFG
3.4.
Types of Recursive Grammars
4.
Frequently Asked Questions
4.1.
What do you mean by ambiguous grammar?
4.2.
What type of grammar can be converted into DFAs?
4.3.
Is there any end symbol in CFG?
4.4.
Which language is accepted by Pushdown automata?
5.
Conclusion
Last Updated: Mar 27, 2024

Context-Free Grammar and Language

Author Naman Kukreja
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
TOC

Introduction

Have you ever wondered if you have a much easier language to use than a regular language and can also somehow help in the programming language?

Then your search is over! Context-Free Language is the answer to your problem. We will learn all about this language in this blog, so let's proceed with our topic without wasting further time.

You can also read about - Moore Machine

Context-Free Grammar(CFG)

You will hear CFG a lot of time in this blog or any other blog related to this topic, so let's first know what CFG is. It stands for Context-Free Grammar.

The grammar is used to create all string patterns from a formal language. It can be defined by using four tuples as shown below:

G = (V, T, P, S)

Also read , Arden's theorem

Explanation

  1. G in the above expression stands for grammar. It consists of the set of all the production rules with the help of which we can generate the string of a language.
  2. T stands for the final set of the terminal symbol. We have to use the lower case alphabet to show them.
  3. V and T are somewhat opposite as V stands for the set of all non-terminal symbols, and we have to use capital letters to denote it.
  4. P is the collection of all the production rules used to replace all non-terminals symbols of a string with terminal or other non-terminal symbols.
  5. S stands for the start symbol, used for deriving string.

Examples

Example 1 

Construct the CFG for having any number of b’s over the set ∑= {b}.

Solution:

The regular expression for the above language is 

r.e. = b*

Production rules are as given below:

S → bS    rule 1  
S → ε     rule 2  

Now, we will derive the string “bbbbbb.”

S  
bS   
bbS          rule 1  
bbbS         rule 1  
bbbbS        rule 1  
bbbbbS       rule 1  
bbbbbbS      rule 1  
bbbbbbε      rule 2  
bbbbbb  

The r.e. = b* can generate a set of string {ε, b, bb, bbb,.....}

Example 2 

Construct a CFG for the expression (0+1)*

Solution:

Production rule (P):  
S → 0S | 1S  
S → ε  

This will result in the set {ε, 0, 1, 01, 10, 00, 11, ....}. 

Example 3

Construct a CFG for language L = {wcwR | where w € (a, b)*}.

Solution:

The production rules can be

S → aSa     rule 1  
S → bSb     rule 2  
S → c       rule 3.  

Now, we can use it to derive different strings. Let’s take an example of the string “abbcbba” 

S → aSa   
S → abSba       from rule 2  
S → abbSbba     from rule 2  
S → abbcbba     from rule 3  

Example 4

Construct a CFG for the language L=anb2n

Solution:

This can generate the following output  {abb, aabbbb, aaabbbbbb....}.

The production rule is 

S → aSbb | abb.  

If we want to derive the string “aabbbb,” we will proceed like this.

S → aSbb  
S → aabbbb    

 

Also see, Turing Machine in TOC.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Application, Properties, and Types of Grammar

Here, we will discuss the applications, properties, and recursive grammar types. 

Applications

CFG has great practical importance. Some of the applications are given below:

  • For defining programming languages.
  • For the construction of compilers
  • For describing Arithmetic expressions
  • For the transition of programming languages.

Properties

Some of the properties of Context-Free language are given below:

  • They are closed under concatenation.
  • They are closed under union.
  • They are not closed under complement and intersection.
  • They are accepted by pushdown automation.

Ambiguity in CFG

CFG is ambiguous as:

  • It has more than one leftmost derivation.
  • It has more than one rightmost derivation.
  • It has more than one parse tree.

Types of Recursive Grammars

There are two types of Recursive Grammar, i.e., Left and Right Recursive grammar.

Left Recursive Grammars: In CFG, if there is a production rule where X->Xa where a is a string of terminals and X is non-terminal, it is known as left recursive production, and the grammar which have left recursive production is known as left recursive grammar.

Right Recursive Grammars: In CFG, if there is a production rule where X->aX where a is a string of terminals and X is non-terminal, it is known as right recursive production, and the grammar which has right recursive production is known as right recursive grammar.

Read About - Simplification of CFG

Frequently Asked Questions

What do you mean by ambiguous grammar?

When the same grammar produces more than one prase tree is known as ambiguous.

What type of grammar can be converted into DFAs?

Right linear grammar can be translated into DFAs.

Is there any end symbol in CFG?

No, there are no end symbols in CFG.

Which language is accepted by Pushdown automata?

Context-free language is accepted by Pushdown automata.

Conclusion

In this article, we have learned about Context-Free Language and Context-Free Grammar, its tuples with examples, and about their properties, applications, and types.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Regular Grammar
Next article
Regular Expression And Finite Automata
Live masterclass