Free Download of VTU 5th Semester Computer Science FAFL Automata related Projects. Do put on a comment to start downloading.
Download here it for free. Free Download here.
Catch me at: http://firstvikram.synthasite.com
Contents
1 Graphical Representation of Daily Routine. 3
2 Set Theory 4
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Basic Operations with Sets . . . . . . . . . . . . . . . . . . . . 4
2.2.1 Union . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 Intersection . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.3 Difference . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.4 Complement . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.5 Catesian Product . . . . . . . . . . . . . . . . . . . . . 5
2.2.6 Power set . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.7 Empty set . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.8 Subset . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.9 Equal set . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Set-theoretic equalities . . . . . . . . . . . . . . . . . . . . . . 6
3 Graph Theory 7
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Graph Variations . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Applications of Graph . . . . . . . . . . . . . . . . . . . . . . 9
3.4.1 Some Common Graphs . . . . . . . . . . . . . . . . . . 9
3.5 Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.6 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1
4 Generating the closure of given characters of given length 12
4.1 The Algorithm: . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2
1 Graphical Representation of Daily
Routine.
Consider the set NODES
W:Wakeup B:breakfast C:college Lib:library L:launch D:dinner Sp:sports
R:read S:sleeping
Q={W,B,C,Lib,L,Sp,R,D,S}
={t1,t2,t3,t4 .. . . tn} Different input times.
q0=W The initial state.
F={S}
We can represent the graph as:
Figure 1: Daily Routine Graphical Representation
3
2 Set Theory
2.1 Introduction
A set is a collection of well-defined objects. Eg: Roses are members
of set Flowers.
Notation:
We write names of sets as,
{0,1}
The set containing 0 and 1
{Vikram, {Mysore}, 59}
The set containing myself, my place and my roll number also forms the set.
{0, 1, 2, ..}
The set containing all the whole numbers, which is an infinite set.
{x: x is an even number}
The set containing the even numbers (i.e., {0, 2, 4, ...}). A set exists as
an entity when there exists valid elements.
2.2 Basic Operations with Sets
2.2.1 Union
Let A and B be sets.
The union of A and B is the set, denoted by A B, whose elements are
exactly those sets belonging to A or belonging to B.
For example, {a, b, c} ∪ {c, d, e} = {a, b, c, d, e}
2.2.2 Intersection
Let A and B be sets.
The intersection of A and B is the set, denoted by A B, whose elements
are exactly those sets belonging to both A and B.
For example,{a, b, c} ∩ {a, c, d, e, f} = {a, c}
2.2.3 Difference
Let A and B be sets.
The (relative) difference of A with B is the set, denoted by A - B, whose
4
elements are exactly those elements of A which do not belong to B.
For example, {a, b, c} - {b, c, d} = {a}.
2.2.4 Complement
Complement of set A relative to set U,denoted by Ac , is the set of all
members of U that are not members of A. This terminology is most commonly
employed when U is a universal set. This operation is also called the set
difference of U and A, denoted U - A.
The complement of {a, b, c} relative to {b, c, d} is {d},
while, conversely, the complement of {b, c, d} relative to {a, b, c} is {a}.
2.2.5 Catesian Product
Let A and B are sets, Cartesian product of A and B, denoted A X B, is the
set whose members are all possible ordered pairs (a,b) where a is a member
of A and b is a member of B.
For example,The Cartesian product of {a, b, c} and {d, e} is
{{a, {a, d}}, {a, {a, e}}, {b, {b, d}}, {b, {b, e}}, {c, {c, d}}, {c, {c, e}}}.
The product of {d, e} and {a, b, c} is
{{d, {a, d}}, {d, {b, d}}, {d, {c, d}}, {e, {a, e}}, {e, {b, e}}, {e, {c, e}}}.
Thus the Cartesian product is not commutative.
2.2.6 Power set
The power set of a set A is the set whose members are all possible subsets of
A.
For example, the powerset of {a, b} is { {}, {a}, {b}, {a, b} }.
2.2.7 Empty set
A set which has no elements is called an empty set or null set and is denoted
by { } or φ.For example the set S that does not contain any element can be
represented as,
S ={ } or S = φ
2.2.8 Subset
A set A is a subset of B if every element of A is in B and is denoted by A⊆B
If A ⊆ B and B contain an element which is not in A,th A is a proper subset
of B and is denoted by A ⊂ B.
5
2.2.9 Equal set
The two sets A and B are same iff A ⊆ B and B ⊆ A i.e.,every element of
set A is in B and every element is in B are the elements of A.
2.3 Set-theoretic equalities
There are a number of general laws about sets which follow from the def-
initions of set- theoretic operations, subsets, etc. Some of the useful set
theoretical operations for any sets X, Y, Z are:
1 Idempotent Laws
(a) X ∪ X = X (b) X ∩ X = X
2 Commutative Laws
(a) X ∪ Y = Y ∪ X (b) X ∩ Y = Y ∩ X
3 Associative Laws
(a) (X ∪ Y) ∪ Z = X ∪ (Y ∪ Z) (b) (X ∩ Y) ∩Z = X (Y Z)
4 Distributive Laws
(a) X ∪ (Y ∩ Z) = (X ∪ Y) ∩ (X ∪ Z) (b) X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z)
5 Identity Laws
(a) X ∪ φ = X (b) X ∪ U = U
(c) X ∩ φ = φ (d) X ∩ U = x
6 Complement Laws
(a) X ∪ X = U (b)(X) = X
(c) X ∩ X = φ (d) X Y = X ∩ Y
7 DeMorgans Laws
(a) (X ∪ Y) = X ∩ Y (b) (X ∩ Y) = X ∪ Y
8 Consistency Principle
(a) X ⊆ Y iff X ∪ Y = Y (b) X ⊆ Y iff X ∩ Y = X
6
3 Graph Theory
3.1 Introduction
Figure 2: simple graph
A graph is a pair of sets (V, E), where:
V is a nonempty set whose elements are called vertices.
E is a collection of twoelement subsets of V called edges.
The vertices correspond to the dots, and the edges correspond to the lines.
Thus, the dotsandlines diagram above is a pictorial representation of the
graph (V, E) where: V = {A, B, C, D, E, F, G}
E = {{A, B} , {A, C} , {B, D} , {C, D} , {C, E} , {E, F } , {E, G} } .
3.2 Definitions
AB is used to denote an edge between vertices A and B rather than the
set notation A, B. Also AB and BA are the same edge, just as A, B and B,
A are the same set.
Two vertices in a graph are said to be adjacent if they are joined by an
edge, and an edge is said to be incident to the vertices it joins. The number
of edges incident to a vertex is called the degree of the vertex. For example,
in the graph above, A is adjacent to B and B is adjacent to D, and the edge
AC is incident to vertices A and C. Vertex H has degree 1, D has degree 2,
and E has degree 3.
Deleting some vertices or edges from a graph leaves a subgraph. Formally,
a subgraph of G = (V, E) is a graph G = (V, E) where V is a nonempty
7
subset of V and E is a subset of E. Since a subgraph is itself a graph, the
endpoints of every edge in E must be vertices in V.
3.3 Graph Variations
There are many variations on the basic notion of a graph. Three particularly
common variations are described below. In a multigraph, there may be more
than one edge be tween a pair of vertices. Here is an example:
Figure 3: multigraph
The edges in a directed graph are arrows pointing to one endpoint or the
other.
Directed graphs are often called digraphs. We denote an edge from vertex
A to vertex B in a digraph by A B. Formally, the edges in a directed graph
are ordered pairs of vertices rather than sets of two vertices. The number
of edges directed into a vertex is called the indegree of the vertex, and the
number of edges directed out is called the outdegree.
One can also allow selfloops, edges with both endpoints at one vertex.
Combinations of these variations are also possible; for example, one could
work with directed multigraphs with selfloops.
Except where stated otherwise, the word graph in this course refers to a
graph without mul tiple edges, directed edges, or selfloops.
8
3.4 Applications of Graph
Graphs are the most useful mathematical objects in computer science.
Some practical situations where graphs arise:
Data Structures Each vertex represents a data object. There is a di-
rected edge from one object to another if the first contains a pointer or
reference to the second.
Attraction Each vertex represents a person, and each edge represents a
romantic attrac tion. The graph could be directed to model the unfortunate
asymmetries.
The Web Each vertex represents a web page. Directed edges between
vertices represent hyperlinks.
Airline Connections Each vertex represents an airport. If there is a
direct flight be tween two airports, then there is an edge between the corre-
sponding vertices. These graphs often appear in airline magazines.
People often put numbers on the edges of a graph, put colors on the ver-
tices, or add other ornaments that capture additional aspects of the phe-
nomenon being modeled. For example, a graph of airline connections might
have numbers on the edges to indicate the duration of the corresponding
flight. The vertices in the attraction graph might be colored to indicate the
persons gender.
3.4.1 Some Common Graphs
Some graphs come up so frequently that they have names. The complete graph
on n vertices, also called Kn , has an edge between every pair of vertices.
Here is K5 :
The empty graph has no edges at all.
3.5 Isomorphism
Two graphs that look the same might actually be different in a formal
sense. For example, the two graphs below are both cycles with 4 vertices:
9
Figure 4: Regular graph
Figure 5: Isomorphism
But one graph has vertex set {A, B, C, D} while the other has vertex set
{1, 2, 3, 4}. If so, then the graphs are different mathematical objects, strictly
speaking. But this is a frustrating distinction; the graphs look the same!
3.6 Connectivity
In the diagram below, the graph on the left has two pieces, while the graph
on the right has just one.
A graph is connected if for every pair of vertices u and v, the graph contains
a path with endpoints u and v as a subgraph. The graph on the left is not
connected because there is no path from any of the top three vertices to either
of the bottom two vertices. However, the graph on the right is connected,
10
Figure 6: Non-connected and Connected Graphs
because there is a path between every pair of vertices.
A maximal, connected subgraph is called a connected component. The
graph on the left has two connected components, the triangle and the single
edge. The graph on the right is entirely connected and thus has a single
connected component.
Source: Internet
11
4 Generating the closure of given characters
of given length
If a set contains a list of alphabets, then the elements can be permuted to
produce the closure of the set of certain lengths.
Example: Consider the set A,
A = {a, b, c}
then A* = A0 ∪ A1 ∪ A2 ∪ ... ∪ An
where,
A* is the closure
A0 is the set of characters of length 0
A1 is the set of characters of length 1
and so on..
Thus,
A0 = { }
A1 = {a, b, c}
A2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc}
and so on...
This permutation logic can be effectly applied using a computer, that
takes the input characters and the length to permute on.
4.1 The Algorithm:
The following algorithm generates the closure of the given characters of given
length. The closures are outputted onto the screen.
void permutation(string, characters, length)
stringLength = length of ’string’
count ← count + 1
if stringLength >= length
return
a ← string
n ← length of ’characters’
for i ← 0 to n
a[i] ← character[i]
permutation(string, characters, length)
return
The equivalent C file, named permutation.c, is included alongwith. It
generates the closure of the given characters.
12
Subscribe to:
Post Comments (Atom)
where is my download?
ReplyDelete