Regular and Non-Regular Grammars

Unit 3

Unit: 3

TAFL

Course Details
(B Tech 4th Sem)

KCS - 402 TAFL Unit Number: 3

1
6/12/2023
Content

• Introduction
• Grammars
• Types of Grammars
• Context-Free Languages
• Context-Free Languages: Example
• Left Most ad Right Most derivations
• Parse Tree
• Ambiguous grammar
• Regular Grammar
• Removal of Unit Productions
• Removal of ɛ Productions
• Chomsky Normal Form
• Greibach Normal Form

6/12/2023 KCS - 402 TAFL Unit Number: 3 2

Course Objective

• Introduce concepts in automata theory and theory of computation

• Identify different formal language classes and their relationships

• Design grammars and recognizers for different formal languages

• Prove or disprove theorems in automata theory using its properties

• Determine the decidability and intractability of computational

problems

6/12/2023 KCS - 402 TAFL Unit Number: 3 3

Unit Objective

• To Understand the Regular Grammar.

• To understand the context free grammar.
• To understand the relationship between FA and Context Free
Grammars.
• To understand the Normal Forms in Grammar .

KCS - 402 TAFL Unit Number: 3

6/12/2023 4
Prerequisite and Recap

Prerequisite:
• Basic concept of rules of grammars of various languages, concept of
tree.

Recap:
• Regular expressions are the way of representation of the FA.
• RE can be converted into FA.
• FA can be converted into regular expressions.
• Any language can be regular or not which will be proved by
Pumping Lemma.

KCS - 402 TAFL Unit Number: 3

6/12/2023 5
Syllabus of Unit 3

Regular and Non-Regular Grammars: Context Free Grammar(CFG)-

Definition, Derivations, Languages, Derivation Trees and Ambiguity,
Regular Grammars-Right Linear and Left Linear grammars, Conversion
of FA into CFG and Regular grammar into FA, Simplification of CFG,
Normal Forms- Chomsky Normal Form(CNF), Greibach Normal Form
(GNF), Chomsky Hierarchy, Programming problems based on the
properties of CFGs.

KCS - 402 TAFL Unit Number: 3

6/12/2023 6
Introduction

Objective: To understand the basic definition of grammar.

A grammar consists of :

• A set of variables (non terminals), one of which is represented as

start symbol; It is customary to use upper case letters for variables.

• A set of terminals ( customary use lower case letters), and

• A list of productions (set of rules).

KCS - 402 TAFL Unit Number: 3

6/12/2023 7
Grammars

A formal definition of a Grammar consists of :

• A finite set of rewriting rules in the form of :

α→β,

where α and β are the strings of symbols.

• A special “initial” symbol S (S for Sentence);

• A finite set of symbols stand for ‘words’ of language called terminal;
[EXAMPLE: a,b,c……+,-…….etc]
• Other symbols stand for ‘phrases’ and are known as non terminals.
*EXAMPLE: A,B,C……+

KCS - 402 TAFL Unit Number: 3

6/12/2023 8
EXAMPLE of GRAMMAR

KCS - 402 TAFL Unit Number: 3

6/12/2023 9
Types of Grammars

KCS - 402 TAFL Unit Number: 3

6/12/2023 10
Types of Grammars (Continued)

KCS - 402 TAFL Unit Number: 3

6/12/2023 11
Context-Free Languages: Syntax

KCS - 402 TAFL Unit Number: 3

6/12/2023 12
Context-Free Languages: Example

KCS - 402 TAFL Unit Number: 3

6/12/2023 13
Examples of CFG

Q1: Write CFG which generates palindrome for binary string.

Palindrome is a string which will be same while reading from LHS or RHS
example 101, 010…..

• S → 0S0/1S1
• S → 0/1/ɛ

Generate 0101010
• S → 0S0 [S → 0S0 ]
• S → 01S10 [S → 1S1 ]
• S → 010S010 [S → 0S0 ]
• S → 0101010[S → 1]

KCS - 402 TAFL Unit Number: 3

6/12/2023 14
Examples of CFG

Q2: Write CFG for regular expression r = 0*1(0+1)*

• r = 0*1(0+1)*
• 0* 1 (0+1)*

• A B

• S →A1B
• A →0A/ɛ
• B →0B/1B/ɛ

KCS - 402 TAFL Unit Number: 3

6/12/2023 15
Examples of CFG (CO1, CO2)

Q3: Write CFG for regular expression r = (a+b)*aa(a+b)*

• S →AaaA
• A →aA/ɛ
• A →bA/ɛ

Q4: Set of al strings of length 2

• R=(a+b)(a+b)
• S →AA
• A →a/b

KCS - 402 TAFL Unit Number: 3

6/12/2023 16
Examples of CFG

Q5: Set of all strings of L=(a+b)*

• S →aS/bS/ɛ

Q6: Set of all strings of length at least 2

• R= (a+b)(a+b)(a+b)*
• S →AAB
• A →a/b
• B →aB/bB/ɛ

Q7: Set of all strings of length at most 2

• R=(a+b+ɛ)(a+b+ɛ)
• S →AA
• A →a/b/ɛ
KCS - 402 TAFL Unit Number: 3
6/12/2023 17
Examples of CFG

Q8: For R= a(a+b)*b

• S →aAb
• A →aA/bA/ɛ

KCS - 402 TAFL Unit Number: 3

6/12/2023 18
Left Most ad Right Most derivations

• A string can be derived in many ways . But we restrict ourselves to :

1. Rightmost Derivations
2. Leftmost Derivations

• In leftmost derivations the left most variable of β from (α→β) , is

picked for expansion.

• In rightmost derivations the right most variable of β from (α→β) , is

picked for expansion.

KCS - 402 TAFL Unit Number: 3

6/12/2023 19
Left Most ad Right Most derivations
[Example]
For the grammar given below :
S →A1B
A →0A|ɛ
B →0B|1B|ɛ
Give Leftmost derivation and rightmost derivation of string 1001.

Solution
Leftmost derivation of 1001:
S →A1B
S →1B *A →ɛ+
→10B *B →0B+
→100B *B →0B+
→1001B *B →1B+
→1001 *B →ɛ+
KCS - 402 TAFL Unit Number: 3
6/12/2023 20
Left Most ad Right Most derivations
[Example] (Continued)
Rightmost derivation of 1001:
S →A1B
S →A10B *B →0B+
→A100B *B →0B+
→A1001B *B →1B+
→A1001 *A →ɛ+
→1001 *B →ɛ]

KCS - 402 TAFL Unit Number: 3

6/12/2023 21
Parse Tree (CO1, CO2)

Recap: Till now we have learned about basic definition of regular

grammar and its types.

Prerequisite: Basic knowledge about Finite Automata and Trees.

Objective: To understand the design of parse tree.

KCS - 402 TAFL Unit Number: 3

6/12/2023 22
Parse Tree (CO1, CO2)

Objective: To understand the design of parse tree

A set of derivations applied to generate a word can be represented

using a tree. Such a tree is known as a parse tree. A parse tree
representation gives us a better understanding of:

• Recursion
• Grouping of symbols

A parse tree is constructed with the following conditions:

• Root of the tree is represented by start symbol.
• Each interior mode is represented by a variable belonging to V.
• Each leaf mode is represented by a terminal or ɛ.
KCS - 402 TAFL Unit Number: 3
6/12/2023 23
Parse Tree [Example]

For a grammar given below S →0S1|01

• Give Parse tree derivation of 000111

• Derivation using parse tree:

S S →0S1

0 S 1 S →0S1

1 S →01
0 S

0 1

KCS - 402 TAFL Unit Number: 3

6/12/2023 24
Ambiguous Grammar (CO1, CO2)

Recap: We have studied about Grammar and its type and Parse Tree.

Prerequisite: Understanding of Grammar.

Objective: To understand the ambiguity of grammar.

KCS - 402 TAFL Unit Number: 3

6/12/2023 25
Ambiguous Grammar (CO1, CO2)

Objective: To understand the ambiguity of grammar.

Context Free Grammars(CFGs) are classified based on:

• Number of Derivation trees

• Number of strings

Depending on Number of Derivation trees, CFGs are sub-divided into 2

types:
• Ambiguous grammars
• Unambiguous grammars

KCS - 402 TAFL Unit Number: 3

6/12/2023 26
Ambiguous grammar:

A CFG is said to ambiguous if there exists more than one derivation

tree for the given input string i.e., more than one Left Most Derivation
Tree (LMDT) or Right Most Derivation Tree (RMDT).

Definition:
G = (V,T,P,S) is a CFG is said to be ambiguous if and only if there exist a
string in T* that has more than on parse tree.

where V is a finite set of variables.

T is a finite set of terminals.
P is a finite set of productions of the form, A -> α, where A is a variable
and α ∈ (V ∪ T)* S is a designated variable called the start symbol.

KCS - 402 TAFL Unit Number: 3

6/12/2023 27
Ambiguous grammar Example:

• S →SS|a|b is ambiguous or not?

• Two parse trees can be generated for the string ‘aab’

• S
S

S S S S

S S b S S
b

a a
a a

KCS - 402 TAFL Unit Number: 3

6/12/2023 28
Regular Grammar (CO1, CO2)

Recap: We have studied about Grammar and its type, Parse Tree and
Ambiguity of grammar.

Prerequisite: Understanding of Grammar.

Objective: To understand the definition of regular grammar.

KCS - 402 TAFL Unit Number: 3

6/12/2023 29
Regular Grammar (CO1, CO2)

Objective: To understand the definition of regular grammar.

The language accepted by finite automata can be described using a set

of productions known as regular grammar. The productions of a
regular grammar are of the following form:
• A→a
• A →aB
• A →Ba
• A→ɛ

Where a ϵ T and A,B ϵ V.

• A language generated by a regular grammar is known as regular
language.
KCS - 402 TAFL Unit Number: 3
6/12/2023 30
Regular Grammar(Continued)
A regular grammar could be written in two forms
• Right Linear Form
• Left Linear Form

Right Linear Form:

A right Linear Form has the productions of form:
• A →a
• A →aB
• A →ɛ

Left Linear Form:

A left Linear Form has the productions of the form:
• A →a
• A →Ba
• A →ɛ
KCS - 402 TAFL Unit Number: 3
6/12/2023 31
DFA to Right Linear Regular Grammar

• Given a DFA:
a

q0 q1

b b b
b
a
q2 q3

KCS - 402 TAFL Unit Number: 3

6/12/2023 32
DFA to Right Linear Regular Grammar (Continued)
• Step 1: Rename the states: for q0 which is start state make it as S.
rest as a non terminals like A,B,C…
a

S A

b b b
b
a
B C

KCS - 402 TAFL Unit Number: 3

6/12/2023 33
DFA to Right Linear Regular Grammar (Continued)
• Step 2: Set of productions are given by:

S A

b b b
b
a
B C

a
• S → aA|bB
• A → aS|bC|b
• B → bs|aC|a
• C → aB|bA KCS - 402 TAFL Unit Number: 3
6/12/2023 34
Right Linear Grammar to DFA
Convert the given Right Linear Grammar to DFA :
• S →bB
• B →bC|b
• B →aB
• C →a

STEP 1: Adding transactions corresponding to every production ,we

get: a
b b
S B C

KCS - 402 TAFL Unit Number: 3

6/12/2023 35
Right Linear Grammar to DFA (Continued)

• STEP 2: Adding a state E to handle Φ transitions , final DFA will be:

KCS - 402 TAFL Unit Number: 3

6/12/2023 36
DFA to Left Linear Grammar

Following steps are required to write a left linear grammar

corresponding to a DFA.

• Interchange starting state and the final state.

• Reverse the direction of all the transactions.
• Write the grammar from the transaction graph in left linear form.

KCS - 402 TAFL Unit Number: 3

6/12/2023 37
DFA to Left Linear Grammar

• Following DFA is Given:

KCS - 402 TAFL Unit Number: 3

6/12/2023 38
DFA to Left Linear Grammar(Continued)

• Interchange the starting state and the final state and reverse the
direction of transactions, we get the transaction graph as following:

• Writing an equivalent left linear grammar, we get:

• S →Ba|Ab, A →Sb|Ca|a
• B →Sa|Cb|b, C →Bb|Aa

KCS - 402 TAFL Unit Number: 3

6/12/2023 39
Left Linear Grammar to DFA

Every left linear grammar can be represented using an equivalent DFA.

Following steps are required to draw a DFA for a given left linear
grammar.

• Draw a transaction graph from the given left linear grammar.

• Reverse the direction of all the transactions.
• Interchange starting state and the final state.
• Carry out conversion from FA to DFA.

KCS - 402 TAFL Unit Number: 3

6/12/2023 40
Left Linear Grammar to DFA (Example)
• Following Linear grammar is given:
• S →Ca|Bb
• C →Bb
• B →Ba|b

• Step 1: Draw a transaction graph from the given left linear

grammar:

• D is an accepting state. It is added for the production B → b

KCS - 402 TAFL Unit Number: 3

6/12/2023 41
Left Linear Grammar to DFA (Example)

• Step 2: Reverse the direction of transaction and interchange

starting state and the final state.

KCS - 402 TAFL Unit Number: 3

6/12/2023 42
Left Linear Grammar to DFA (Example)

• Conversion from FA to DFA:

KCS - 402 TAFL Unit Number: 3

6/12/2023 43
Right Linear Grammar to Left Linear
Grammar (CO1, CO2)
• Following Right Linear grammar is given:

• Step 1: Conversion of Right Linear grammar to transaction system.

KCS - 402 TAFL Unit Number: 3

6/12/2023 44
Right Linear Grammar to Left Linear
Grammar (Continued)
• Step 2: Interchange the start state with the final state and reversing
direction of transitions, we get:

• Write the left linear grammar from the transaction diagram:

• S →b|Bb|Ca
• B →Ba|b
• C →Bb
KCS - 402 TAFL Unit Number: 3
6/12/2023 45
Left Linear Grammar to Right Linear
Grammar
A left Linear Grammar is given:
• S →C0|A0|B1
• A →A1|C0|B1|0
• B →B1|1
• C →A0
Step 1: Transition system for the left linear grammar if constructed:

KCS - 402 TAFL Unit Number: 3

6/12/2023 46
Left Linear Grammar to Right Linear
Grammar (Continued)
• Step 2: Interchange the start state and the final state and changing
direction of all transactions:

• Step 3: Following grammar we get:

• S →1B|0A
• A →0C|1A|0
• B →1B|1A|1
• C →0C|0
KCS - 402 TAFL Unit Number: 3
6/12/2023 47
Removal of Unit Productions

• Any production rule in the form A → B where A, B ∈ Non-terminal is

called unit production.

Removal Procedure −
• Step 1 − To remove A → B, add production A → x to the grammar
rule whenever B → x occurs in the grammar. [x ∈ Terminal, x can be
Null]
• Step 2 − Delete A → B from the grammar.
• Step 3 − Repeat from step 1 until all unit productions are removed.

KCS - 402 TAFL Unit Number: 3

6/12/2023 48
Removal of Unit Productions
Problem
Remove unit production from the following −
S → XY,
X → a,
Y → Z | b,
Z → M,
M → N,
N→a
Solution −
There are 3 unit productions in the grammar −
• Y → Z, Z → M, and M → N
At first, we will remove M → N.
• As N → a, we add M → a, and M → N is removed.
The production set becomes
• S → XY, X → a, Y → Z | b, Z → M, M → a, N → a
KCS - 402 TAFL Unit Number: 3
6/12/2023 49
Removal of Unit Productions (Continued)

Now we will remove Z → M.

• As M → a, we add Z→ a, and Z → M is removed.
The production set becomes
• S → XY, X → a, Y → Z | b, Z → a, M → a, N → a
Now we will remove Y → Z.
• As Z → a, we add Y→ a, and Y → Z is removed.
The production set becomes
• S → XY, X → a, Y → a | b, Z → a, M → a, N → a
• Now Z, M, and N are unreachable, hence we can remove those.
The final CFG is unit production free −
• S → XY, X → a, Y → a | b

KCS - 402 TAFL Unit Number: 3

6/12/2023 50
Removal of ɛ Productions

Given Grammar:
• S→aA
• A →b|ɛ

Solution:
• Substitute ɛ on production S→aA
• S→a*ɛ+
• S→a

• Then add this production into main one:

• S→aA|a
• A →b

KCS - 402 TAFL Unit Number: 3

6/12/2023 51
Chomsky Normal Form (CO1, CO2)

Recap: Till now we have studied about grammar, Context Free

Grammar and Regular Grammar.

Prerequisite: Basic knowledge of CFG and Regular Grammar.

Objective: To understand the definition on Chomsky Normal Form.

KCS - 402 TAFL Unit Number: 3

6/12/2023 52
Chomsky Normal Form (CO1, CO2)

Objective: To understand the definition on Chomsky Normal Form.

A CFG is in Chomsky Normal Form if the Productions are in the

following forms −
• A→a
• A → BC
• S→ε
where A, B, and C are non-terminals and a is terminal.

KCS - 402 TAFL Unit Number: 3

6/12/2023 53
Algorithm to Convert into Chomsky Normal
Form
Step 1 − If the start symbol S occurs on some right side, create a new start
symbol S’ and a new production S’→ S.
Step 2 − Remove Null productions. (Using the Null production removal
algorithm discussed earlier)
Step 3 − Remove unit productions. (Using the Unit production removal
algorithm discussed earlier)
Step 4 − Replace each production A → B1…Bn where n > 2 with A → B1C
where C → B2 …Bn. Repeat this step for all productions having two or more
symbols in the right side.
Step 5 − If the right side of any production is in the form A → aB where a is a
terminal and A, B are non-terminal, then the production is replaced by A →
XB and X → a. Repeat this step for every production which is in the form A →
aB.

KCS - 402 TAFL Unit Number: 3

6/12/2023 54
Chomsky Normal Form(Continued)

Problem

• Convert the following CFG into CNF

• S → ASA | aB, A → B | S, B → b | ε

Solution

(1) Since S appears in R.H.S, we add a new state S0 and S0→S is added
to the production set and it becomes −

S0→S, S→ ASA | aB, A → B | S, B → b | ∈

KCS - 402 TAFL Unit Number: 3

6/12/2023 55
Chomsky Normal Form(Continued)

(2) Now we will remove the null productions −

• B → ∈ and A → ∈

After removing B → ε, the production set becomes −

• S0→S, S→ ASA | aB | a, A → B | S | ∈, B → b

After removing A → ∈, the production set becomes −

• S0→S, S→ ASA | aB | a | AS | SA | S, A → B | S, B → b

KCS - 402 TAFL Unit Number: 3

6/12/2023 56
Chomsky Normal Form(Continued)

(3) Now we will remove the unit productions.

After removing S → S, the production set becomes −
• S0→S, S→ ASA | aB | a | AS | SA, A → B | S, B → b
After removing S0→ S, the production set becomes −
• S0→ ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
• A → B | S, B → b
After removing A→ B, the production set becomes −
• S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
• A→S|b
• B→b
After removing A→ S, the production set becomes −
• S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
• A → b |ASA | aB | a | AS | SA, B → b

KCS - 402 TAFL Unit Number: 3

6/12/2023 57
Chomsky Normal Form(Continued)

(4) Now we will find out more than two variables in the R.H.S

Here, S0→ ASA, S → ASA, A→ ASA violates two Non-terminals in R.H.S.

Hence we will apply step 4 and step 5 to get the following final
production set which is in CNF −

• S0→ AX | aB | a | AS | SA
• S→ AX | aB | a | AS | SA
• A → b |AX | aB | a | AS | SA
• B→b
• X → SA

KCS - 402 TAFL Unit Number: 3

6/12/2023 58
Chomsky Normal Form(Continued)

(5) We have to change the productions S0→ aB, S→ aB, A→ aB

And the final production set becomes −

• S0→ AX | YB | a | AS | SA
• S→ AX | YB | a | AS | SA
• A → b A → b |AX | YB | a | AS | SA
• B→b
• X → SA
• Y→a

KCS - 402 TAFL Unit Number: 3

6/12/2023 59
Greibach Normal Form (CO1, CO2)

Recap: Till now we have studied about grammar, Context Free

Grammar and Regular Grammar.

Prerequisite: Basic knowledge of CFG and Regular Grammar.

Objective: To understand the definition on Greibach Normal Form.

KCS - 402 TAFL Unit Number: 3

6/12/2023 60
Greibach Normal Form (CO1, CO2)

Objective: To understand the definition on Greibach Normal Form.

A CFG is in Greibach Normal Form if the Productions are in the

following forms −

• A→b
• A → bD1…Dn
• S→ε

where A, D1,....,Dn are non-terminals and b is a terminal.

KCS - 402 TAFL Unit Number: 3

6/12/2023 61
Algorithm to Convert a CFG into Greibach
Normal Form
Step 1 − If the start symbol S occurs on some right side, create a new
start symbol S’ and a new production S’ → S.

Step 2 − Remove Null productions. (Using the Null production removal

algorithm discussed earlier)

Step 3 − Remove unit productions. (Using the Unit production removal

algorithm discussed earlier)

Step 4 − Remove all direct and indirect left-recursion.

Step 5 − Do proper substitutions of productions to convert it into the

proper form of GNF.
KCS - 402 TAFL Unit Number: 3
6/12/2023 62
Greibach Normal Form(Continued)

Question:

Convert the following CFG into CNF

• S → XY | Xn | p
• X → mX | m
• Y → Xn | o

KCS - 402 TAFL Unit Number: 3

6/12/2023 63
Greibach Normal Form(Continued)
Solution
Here, S does not appear on the right side of any production and there are no
unit or null productions in the production rule set. So, we can skip Step 1 to
Step 3.
Now after replacing
X in S → XY | Xo | p
with
• mX | m
we obtain
• S → mXY | mY | mXo | mo | p.
And after replacing
• X in Y → Xn | o
with the right side of
• X → mX | m
we obtain
• Y → mXn | mn | o.
KCS - 402 TAFL Unit Number: 3
6/12/2023 64
Greibach Normal Form(Continued)

Two new productions O → o and P → p are added to the production

set and then we came to the final GNF as the following −

• S → mXY | mY | mXC | mC | p
• X → mX | m
• Y → mXD | mD | o
• O→o
• P→p

KCS - 402 TAFL Unit Number: 3

6/12/2023 65
Daily Quiz

1. Let G be the grammar S → aB | bA, A →a | aS | bAA, B → b | bS | aBB.

For the string aaabbabbba find
a. Parse tree
b. Leftmost derivation
c. Rightmost derivation
d. Is the grammar unambiguous?
2. Write the grammar generating the language L = {anbm | where n≠m}
3. Define the Chomsky Normal Form (CNF). Convert the grammar given
below to its equivalent CNF:
• S → ABA
• A → 0A | є
• B → 1B | є
4. Using pumping lemma for CFLs prove that language is not Context Free.
n2
L  0 , n  1

6/12/2023 KCS - 402 TAFL Unit Number: 3 66

Daily Quiz (Continued)

5. The following grammar generates the regular expression 0*1(0+1)*

S→A1B
A→0A| ɛ
B→0B|1B|ɛ
Give leftmost and rightmost derivation of the string 00101
6. Give the CFG of the following language:
0(0+1)*01(0+1)*1
7. Find the CFG of following language
L={aibjck|i=j+k}
8. Give CFG for matching parenthesis.
9. Give CFG for all strings with at least two 0s, over an alphabet {0,1}.
10. Write an equivalent right recursive grammar for the given left recursive
grammar: S→S10|0

6/12/2023 KCS - 402 TAFL Unit Number: 3 67

MCQ s

1. The alphabet over which the language is defined is represented in CFG

as:
a. non-terminals
b. terminals
c. star symbols
d. Productions

2. In a CFG left hand side production is

a. a single non terminal

b. a single terminal
c. two non-terminals
d. combination of terminals and non-terminals

6/12/2023 KCS - 402 TAFL Unit Number: 3 68

MCQ s( Continued)

3. Which one is not a CFG?

a. S→a
b. aA→b
c. S→aA
d. S→Sb

4. Following productions represent which language: A→a, A→b

a. {ab}
b. {ba}
c. {a,b}
d. {a}

6/12/2023 KCS - 402 TAFL Unit Number: 3 69

MCQ s( Continued)

5. Which one is a unit production?

a. A→B
b. A→aB
c. A→Bb
d. A→a

6. the production S→ABC can be converted to S→AX by adding

a. S→AB
b. X→BC
c. X→AB
d. X→ABC

7. In parse tree the interior nodes are:

a. starting symbol
b. terminal
c. non terminal except start symbol
d. null symbol

6/12/2023 KCS - 402 TAFL Unit Number: 3 70

MCQ s( Continued)
8. Terminals can be only in ………. in case of parse tree:
a. root
b. leaves
c. nodes
d. none of these

9. In case of productions A→aB, A→a the state B is in :

a. initial
b. final
c. intermediate
d. Dead

10. in case of a CFG in regular form the productions should be in which form:
a. A→aB|a
b. A→Ba
c. A→a
d. A→CV
6/12/2023 KCS - 402 TAFL Unit Number: 3 71
Expected Questions for University Exam

1. Let G = ({ S,C},{a,b},P,S) where P consistes of S→aCa,

C→aCa|b. Find L(G).
2. Find L(G), where G = (, S-,,0,1-,,S→0S1, S→ɛ},S)
3. Find out the context free language
• S→aSb|aAb
• A→bAa
• A→ba
4. Give the CFG of the following language:
0(0+1)*01(0+1)*1
5. Give CFG for matching parenthesis.

6/12/2023 KCS - 402 TAFL Unit Number: 3 72

Summary

• There are basically two types of derivations of strings from the

grammar, namely, top down derivations and bottom up derivations.
• Parse tree can be constructed for each derivations.
• Ambiguous grammars and normal forms for the grammars were
also discussed in this unit.

6/12/2023 KCS - 402 TAFL Unit Number: 3 73

References

1. Aho, Hopcroft and Ullman, The Design and Analysis of Computer

Algorithms, Addison Wesley.
2. Aho, Sethi, Ullman, Compilers Principles, Techniques and Tools,
Pearson Education, 2003.
3. Hopcroft and Ullman, Introduction to Automata Theory, Languages
and Computation, Addison Wesley.
4. Kohavi, ZVI, Switching And Finite Automata Theory, Tata McGraw-
Hill, 2006.
5. Lewis and Papadimitriou, Elements of the Theory of Computation,
Prentice-Hall.
6. Martin, Introduction to Languages and the Theory of Computation,
McGraw-Hill, 2nd edition,1996.
7. Mishra, KLP, Chandrasekaran, N. Theory of Computer Science,
(Automata, Languages and Computation) PHI, 2002.

6/12/2023 KCS - 402 TAFL Unit Number: 3 74

6/12/2023 KCS - 402 TAFL Unit Number: 3 75