Subjects
Applied Mathematics for Electrical Engineering - 3130908
Complex Variables and Partial Differential Equations - 3130005
Engineering Graphics and Design - 3110013
Basic Electronics - 3110016
Mathematics-II - 3110015
Basic Civil Engineering - 3110004
Physics Group - II - 3110018
Basic Electrical Engineering - 3110005
Basic Mechanical Engineering - 3110006
Programming for Problem Solving - 3110003
Physics Group - I - 3110011
Mathematics-I - 3110014
English - 3110002
Environmental Science - 3110007
Software Engineering - 2160701
Data Structure - 2130702
Database Management Systems - 2130703
Operating System - 2140702
Advanced Java - 2160707
Compiler Design - 2170701
Data Mining And Business Intelligence - 2170715
Information And Network Security - 2170709
Mobile Computing And Wireless Communication - 2170710
Theory Of Computation - 2160704
Semester
Semester - 1
Semester - 2
Semester - 3
Semester - 4
Semester - 5
Semester - 6
Semester - 7
Semester - 8
Theory Of Computation
(2160704)
TOC-2160704
Winter-2018
3-b
BE | Semester-
7
Winter-2018
|
27/11/2018
Q3) (b)
4 Marks
Explain Union Rule and Concatenation Rule for Context Free Grammar
Union Rule
If L
1
and L
2
are context - free languages, then the languages L
1
U L
2
is also CFL(context - free languages).
Union : G
u
= (V
u
, Σ, S
u
, P
u
)
A grammar G
u
= (V
u
, Σ, S
u
, P
u
) generating L
1
U L
2
.
First we rename the element of V
2
if necessary so that V
1
n V
2
= ∅
V
u
= V
1
U V
2
U {S
u
}
Where S
u
is a new symbol not in V
1
or V
2
.
Then we let P
u
= P
1
U P
2
U { S
u
--> S
1
| S
2
}
On the other hand, if x is derivable from S
u
in G
u
, the first step in any derivation must be
S
u
-> S
1
or S
u
-> S
2
In the first case, all subsequent productions used must be productions in G
1
, because no variables in V
2
are involved, and thus x ∈ L
1
; in the second case, x ∈ L
2
. Therefore,
L(G
u
) ⊆ L
1
U L
2
Concatenation
If L
1
and L
2
are context - free languages, then the languages L
1
L
2
is also CFL(context - free languages).
Concatenation G
c
= (V
c
, Σ, S
c
, P
c
)
A grammar G
c
= (V
c
, Σ, S
c
, P
c
) generating L
1
L
2
.
Again we relabeled variables if necessary so that V
1
∩ V
2
= ∅ and
define V
c
= V
1
∪ V
2
∪ {S
c
}
This time we let
P
c
= P
1
∪ P
2
∪ { S
c
-> S
1
S
2
}
If x ∈ L
1
L
2
then x = x
1
x
2
, where x
i
∈ L
i
for each i. we may then derive x in G
c
as follows:
S
c
-> S
1
S
2
-> *x
1
S
2
-> * x
1
x
2
= x
First step in the derivation must be Sc -> S
1
S
2
Where the second step is the derivation of x
1
in G
1
and the third step is the derivation of x
2
in G
2
. So x ∈ L
1
L
2
Questions
Go to Question Paper
Q1
(a)
(b)
(c)
Q2
(a)
(b)
(c)
(c)
(OR)
Q3
(a)
(b)
(c)
Q3
(a)
(OR)
(b)
(OR)
(c)
(OR)
Q4
(a)
(b)
(c)
Q4
(a)
(OR)
(b)
(OR)
(c)
(OR)
Q5
(a)
(b)
(c)
Q5
(a)
(OR)
(b)
(OR)
(c)
(OR)