Context Free Grammar CFG in theory of automata

By: Prof. Fazal Rehman Shamil | Whatsapp:+923028700085

What is Context-Free Grammar CFG?

CFG is a set of rules for automating the machine and generating the strings of a language. CFG generates a pattern of strings.

CFG has the following parts;

  1. Start symbol
  2. Set of terminal symbols
  3. Set of non-terminal symbols
  4. Set of rules

CFG Tutorials

In easy words, CFG has the following parts;

  1. Starters
  2. Extraction
  3. Compressors
  4. Values
  5. Operators
  6. Terminators

Starters: Starter is the initial compressed variable. CFG have one starting point. Starters are always on left side of the CFG.

Extraction: The extract form of a compressor. The extraction can have alphabets, starters, compressors, values, operators, and terminator etc.It is represented on right side of the CFG.

Compressors: We can extract the Compressor if extraction is required.It is represented on the left side of the CFG.

Values: Value is a string or set of values combine to make a string.

Or operator: Or operator | is used to represent the or operation. For example 0 | 1 can be read as 0 or 1.

Terminators: The ending point of the CFG. More than one options of ending a CFG are possible but while reading a string CFG must end with a one terminator.

Example

Language: of all strings having many 0’s, defined over {0}

Regular Expression: a+

Context Free Grammar: S ⇒ 0S | 0

Example 

Language: of all strings having many 0’s or no zero, defined over {0}

Regular Expression: a*

Context Free Grammar: S ⇒ 0S | ε

Example 

Language: of all strings having exactly one 0’s or exactly one 1, defined over {0,1}

Regular Expression: 0+1

Context Free Grammar: S ⇒ 0 | 1

Example 

Language: of all strings having many 0’s or many 1’s or no zero or no one, defined over {0,1}

Regular Expression: (0+1)*

Context Free Grammar: S ⇒ 0S | 1S | ε

Examples of CFG

Example 1

Context free grammar

  • Starters : start
  • Extraction: X1X, 0X, Epsilon
  • Compressors: start, X
  • Values: 1, 0, Epsilon
  • Terminators: Epsilon

Example 2

CFG Diagram

CFG

  • Starters : start
  • Extraction: 0,1X, 0X,Eosilon
  • Compressors: start, X
  • Values: 1, 0, Epsilon
  • Terminators: 0, Epsilon

Example 3

Context free Grammar Diagram

  • Starters : start
  • Extraction: x111X, 0X,1X,Eosilon
  • Compressors: start, X
  • Values: 1, 0, Epsilon
  • Terminators: Epsilon

Example 4

context free language

  • Starters : start
  • Extraction: 0X, 11X, Eosilon
  • Compressors: start, X
  • Values: 11, 0, Epsilon
  • Terminators: Epsilon

Example 5

Context freea grammar in compiler design

Example 6

unambigiuous grammar

Example 7

cfg grammar

Example 8

regular grammar in automata

Example 9

simplification of cfg

Example 10

CFG Examples in Automata Theory

Example 11

Examples of CFG Compiler Construction

Example 12

Context Free Grammer TAFL TOC

Video Lecture of Introduction

Video Lecture of Examples

Built the CFG for the language of all those strings having 0 a’s or many a’s?

S ⇒ aS | ε

Now we can read multiple a’s from this CFG.

For example;

To read o a’s from S ⇒ aS | ε

S ⇒ aS | ε

S⇒ ε

To read 1 a from S ⇒ aS | ε

S ⇒ aS

S⇒ a ε

S⇒ a 

To read 2 a from S ⇒ aS | ε

S ⇒ aS

S ⇒ aaS

S⇒ a ε

S⇒ a 

and similarly, we can read many a’s from this CFG.