How to use GNU Emacs for the first time?

Emacs for Beginners...

Using .gdbinit
In order to run executable file with gdb with initializations, specify a initialization file '.gdbinit',
which takes up the normal initializations.
Simple .gdbinit file:
$ cat .gdbinit
1 file a.out
2 set args
3 b a.c:451
4 b a.c:455
Now gdb can be run without any filenames or parameters as,
$gdb or
$gdb -tui        (Terminal User Interface)
This runs the program within gdb by setting breakpoints and arguments (none here) as specified
in .gdbinit. Inputs can also be initialized, from other files too, using .gdbinit.
Create a file named “input”, using an editor indeed, which contains the initial value inputs. Pass it
as an argumment to .gdbinit as
set args < input        (line 2 of previous example)
Commands can also be initialized as:
b r.c:451
p *t
.
.
run
GDB thus initialises inputs, breakpoints and also commands that are used frequently using the
.gdbinit. .gdbinit can be used to such an extent that even macros, functions can be used.
Consider this “input” and .gdbinit files for some program and hope for some logical errors in source
code. I am `cat`ting them as,
$cat input
1 268
25
3B
4 18000
Let this be an input that initializes ID, semester, section and fee.
$cat .gdbinit
1 file semester.out
2 set args < input
3 b semester.c:135
4 b semester.c:534
5 b semester.c:73 if (fee == 125000)
.
.
13 p *student
I hope its self explanatory except line 5, which breaks only if the condition is satisfied.
SJCE/CS&E/VikramTV                                                                                       1
 



$gdb or
$gdb -tui
gdb starts executing semester.out. It provides inputs from file input, creates breakpoints and starts
running. The required instruction to debug, in a huge code, can be reached in no time with proper
initializations with .gdbinit.
There is no manual page for .gdbinit. You may need to refer external sources for further help.
Defining macros or funcitons or loopings in .gdbinit are same as with shell programming.
 



Using GDB under GNU Emacs:
Emacs is an environment. It can be used to write source codes, run it and also debug within it and if
you are bored, you can even play some simple games within it. It uses buffers to handle tasks.
Emacs uses Escape, Control (C) and Meta (M – Meta key or Edit key or Alt key) as the basic tools.
Every shortcut is prefixed with either C or M or their combination. Emacs works using buffers.
To start using Emacs, ofcourse Emacs should be installed, type:
$emacs filename          (starts the Emacs window)
Press C-p and write or edit the source code.
Save it using C-x C-s combination or the dropdown menus can be used.
M-! takes to shell.
Compile source code under a suitable directory using
         gcc -g filename
Press -x or M-x and type 'gdb'.
Emacs can now be used to debug with gdb. If there is a .gdbinit file, Emacs starts debugging with
initializations, else the executable should be provided. Debugging commands using gdb within
Emacs are the same.
To quit using Emacs, press C-x C-c.

My Sorting Algorithm ;) - the 'x'sort. Can you name it??

Catch me at: http://firstvikram.synthasite.com
and also at  : http://tvvikram.blogspot.com

You can find this page at google knol too.

THE 'x' SORT ALGORITHM - Do name it!!!

In this sorting technique, the adjacent elements are compared and sorted. This adjacency continues for every alternative elements of the sequence.
Consider the sequence,
3 6 5 1 9 7 4
On first pass,


{3 6} {5 1} {9 7} {4 }


are grouped and sorted internally. 4 is left alone.
Now,


{3 6} {5 1} {7 9} {4 }


is the sequence.


Let the above sorting be called the 'even' sort.


Starting from the second element or from rightmost end,


{ 3} {6 5} {1 7} {9 4}


On sorting the above sequence internally,


3 5 6 1 7 9 4


is obtained. Let this be called the 'odd' sort. Performing such 'even' and 'odd' sorts alternatively by grouping appropriately, the required sorted sequence is obtained.


The Algorithm:


for k looping 'n-1' times [the algorithm worked fine for n/2 iterations]


[start with 1^st or 2^nd element]
if count = even number, make j = 1
else make j = 2
for j looping n – 1 times
compare adjacent elements and swap if necessary
and increment j by 2 [end of inner loop]
finally increment count by 1 [end of outer loop]




On running 'time' command, the following details were seen:

Number of Elements	Time Taken
1000	0 sec 4 ms
10,000	0 sec 254 ms
100,000	25 sec 560 ms
1,000,000	More than 15 min

Machine: 2.4 GHz Core2Duo Processors


Though the time taken was very high, interesting results were obtained by decreasing the number of outer loops to n/4, n/8, n/16, etc. The time taken was greatly reduced by such iterations (there should be randomly generated numbers).
Keeping the outer loop to n/36 (an arbitrary value), time taken for 10 lakh numbers was 2min and 25.560 sec.

SJCE/CS4/DAA/XSORT 1

The basic sorts in Engineering - Bubble, Selection, Heap and Quick Sorts

Free download of Sorting Algorithms.  Do put on a comment to start downloading.

Download Project Sorting Algorithms for free here.

Download Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort and Heap Sorts for free here.  Computer Science and Engineering, Karnataka - Free Downloads.

Free download here.

Catch me at: http://firstvikram.synthasite.com
and also at  : http://tvvikram.blogspot.com


You may find this report with graphs at:
http://knol.google.com/k/sorting-algorithms#

The Architecture:
April 14, 2009

    The basic architecture of sortings done here consists of a header file sor-
tutil.h, which includes a class named SORT - containing the basic utilities on
array functions such as to generate random numbers - genRand(), printing the
array printArray() and to check if the array elements are in non-descending
order checkSort(). These functions are basic to every array containing integer
numbers. For sake of simplicity, only integer values are used.
    The SORT class also inherits another class named sortdefinitions from file
sortdefinitions.h. The sortdefinitions.h file acts like a source of all the codes of
the sorting techniques done here. It includes the function definitions of all the
sorting techniques, heap sort, quick sort, bubble sort, selection sort, and thus
the two classes SORT and sortdefinitions forms the header file sortutil.h.
    A main function is just written for every sorting technique by including the
header file sortutil.h. Thus there are four main’s for every sort. The basic idea
here was to use the resources provided by the sortutil.h file and perform the nec-
essary tasks. A word on main: A pointer to array has been used to dynamically
allocate the size. A file pointer (fp) has been used to write the runtimes to a file,
say, heap.dat, which eases to plot the graph. Each time the size of the array
is incremented by an OFFSET value, the value being between RANGELOW
and RANGEHIGH. A simple call to genRand with size ’i’ will fetch ’i’ random
numbers into the array ’a’. All printArray calls can be unmasked to view the
elements of the array, obviously when the size of array is very low. Then their
is call to get the present time in seconds and microseconds, the start time of
heap sorting. On calling heapSort, the ’i’ elements of the array are heap sorted.
Finally the end time is obtained from a call to gettimeofday. RunTime is cal-
culated by subtracting start time from end time. The runtime is displayed on
console as well as written to the file only if checkSort is successful. The array
size is incremented and the process is iterated.
Running script:
1. Change to the sorts directory
2. Run the shell script by typing ./run at command prompt
3. Type a filename in *.cpp format [say, heap.cpp]
4. Script terminates by plotting the graph
                                        

THE SORTING ALGORITHMS
              By
           VIKRAM
          SHARAD
        KIRANKUMAR
        PRABHAKAR
            4/2009

                              Contents
1 BUBBLE SORT:                                                                2
  1.1 The Algorithm: . . . . . . . . . . . . . . . . . . . . . . . . . . . .  2
  1.2 Worst Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  3
  1.3 Best Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 SELECTION SORT                                                              4
  2.1 The Algorithm: . . . . . . . . . . . . . . . . . . . . . . . . . . . .  4
  2.2 Worst Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  4
  2.3 Best Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 THE HEAP SORT                                                               6
  3.1 The Algorithm: . . . . . . . . . . . . . . . . . . . . . . . . . . . .  6
  3.2 Analysis of Run Times: . . . . . . . . . . . . . . . . . . . . . . .    7
4 QUICK SORT                                                                  8
  4.1 Worst Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  8
  4.2 Best Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
                                     1


     
                  1    BUBBLE SORT:
Bubble sort is a simple sorting algorithm use to sort the elements. It works
by repeatedly stepping through the list to be sorted, comparing two items at
a time and swapping them if they are in the wrong order. The pass through
the list is repeated until no swaps are needed, which indicates that the list is
sorted. The algorithm gets its name from the way smaller elements bubble to
the top of the list. Because it only uses comparisons to operate on elements, it
is a comparison sort.
1.1     The Algorithm:
    BUBBLESORT(A ,n)
      for i = 1 to n
         for j = 0 to ( n – i )
            if A[ j ] > A[j + 1]
                  A[ j ] ⇔ A[j + 1]
Bubble sort has worst-case and average complexity both (n2 ), where n is the
number of items being sorted. Even other (n2 ) sorting algorithms, such as
insertion sort, tend to have better performance than bubble sort. Therefore
bubble sort is not a practical sorting algorithm when n is large.
                         Figure 1: Gnuplot for bubble sort
                                         2




Consider test case with numbers – 4 2 5 1 2 and on each iteration of inner loop,
(2 4 5 1 2)→ (2 4 5 1 2)→ (2 4 1 5 2)→ (2 4 1 2 5)→ (2 4 1 2 5)→ (2 1 4 2 5)→
(2 1 2 4 5)→ (1 2 2 4 5)→ (1 2 2 4 5)→ (1 2 2 4 5)
1.2     Worst Case
The worst case occurs when the elements are sorted in non-ascending order,
because the largest element need to bubbled till last and hence the worst case
is O(n2 ) time. The graph for worst case is shown in the figure.
1.3     Best Case
The best case occurs when the elements are already sorted, because largest
element is already in right place and needs no swapping. This case takes O(n)
time. The graph for best case is shown in the figure.
                                       3




                      2     SELECTION SORT
Selection sort is one of simplest sorting technique in which we select smallest
item in the list and exchange it with the first item.Obtain the second smallest
element in the list and exchange it with the second element and so on.Finally
all the items will be arranged in ascending order.In otherwords selection sort
performs sorting by repeatly putting the largest element in the unprocessed
portion of the array to the end of the this unprocessed portion until the whole
array is sorted.
2.1     The Algorithm:
         for i←1 to n – 1
              do pos ← i
              for j ← i + 1 to n
                  if A[j] < A[pos]
                      then pos←j
              if pos = i
                  then A[i] ⇔ A[pos]
Selection sort has two loops each of which execute n times. Hence the selection
sort is O(n2 ). The current element is assumed to be the smallest and is compared
with remaining elements. The position of the smallest element is found. If the
smallest element is not the current position, then the two elements are swapped.
Consider a test case with elements – 45 20 40 5 15
(45 20 40 5 15 )→ (5 20 40 45 15) → (5 15 40 45 20)→
(5 15 20 45 40) → (5 15 20 40 45)
2.2     Worst Case
Worst case occurs if the elements are already sorted in the non-ascending order,
because for each iteration the smallest element needs to be swapped and thus
the Worst Case is O(n2 ).
2.3     Best Case
Best case occurs if the elemsnts are already sorted in non-descending order, be-
cause current element is smallest and no element needs to be swapped and thus
the Best Case is O(n).
                                          4



Figure 2: Gnuplot for selection sort
                5




                       3     THE HEAP SORT
This sorting technique builds a max heap tree, in which none of the parent
nodes are smaller than their children, and then sorts the elements by extracting
the topmost element. A sequence of events takes place in this sorting. First the
main function calls ’heapSort’, which in turn calls buildMaxHeap. This is the
basic tool for building the max heap. It builds the max heap tree from the lower
nodes to the root by calling the maxHeap function. maxHeap function checks
always that parent is larger than their children, and if the property is violated
the largest child is exchanged with the parent.
3.1     The Algorithm:
LEFT(i)
         return 2i + 1
RIGHT(i)
         return 2i + 2
MAX-HEAPIFY(A, i)
         l ← LEFT(i)
         r ← RIGHT(i)
         if l ≤ size[A] and A[l] > A[i]
              then largest ← l
              else largest ← i
         if r ≤ size[A] and A[r] > A[largest]
              thenlargest ← r
         if largest = i
              then exchange A[i] ⇔ A[largest]
                  MAX-HEAPIFY(A,largest)
The recurence relation for MAX-HEAPIFY is T(n) ≤ T(2n/3) + Θ(1), since
each childern’s subtrees have a size at most 2n/3 – the worst case being when
the last row of the tree is exactly half full. Thus MAX-HEAPIFY takes T(n) =
O(lg n).
BUILD-MAX-HEAP(A)
         for i ← n/2 downto 1
              do MAX-HEAPIFY(A,i)
BUILD-MAX-HEAP takes O(n) time.
                                          6



HEAP-SORT(A)
         BUILD-MAX-HEAP(A)
         for i ← n downto 2
             do exchange A[1] ⇔ A[i]
                 n←n–1
                 MAX-HEAPIFY(A,1)
HEAP-SORT takes O(n lg n) time since call to BUILD-MAX-HEAP takes O(n)
time and each of the n–1 calls to MAX-HEAPIFY takes O(lg n) time.
For the elements - 10, 5, 16, 8, 68, 21, 43; the heapSort procedure results in a
non-descendingly sorted elements. The state of the elements at each instance
within heapSort iterative with i from number of elements to 2 is:
(10 5 16 8 68 21 43)→ (16 10 43 8 5 21 68)→ (16 10 21 8 5 43 68)→
( 5 10 16 8 21 43 68)→ ( 8 10 5 16 21 43 68)→ ( 5 8 10 16 21 43 68)→
( 5 8 10 16 21 43 68)
                       Figure 3: GnuPlot for Heap Sort
3.2    Analysis of Run Times:
Any of General, Worst or Best Cases of inputs need O(n) time to BUILD-MAX-
HEAP. Further, any of ”add” or ”remove” operations takes O(lg n) time. Hence,
runtimes for heap sorting in all the three cases is always same with O(n lg n)
time.
                                        7



                             4    QUICK SORT
Quick Sort is based on the technique ’Divide and Conquer’. It divides the ele-
ments into two parts and then sorts them. This sorting is continued recursively
till all the elements are sorted. Quick Sort has been implemented using two
functions - Partition and QuickSort.
Paritition routine takes the middle element as pivot, rearranging elements such
that elements smaller than the pivot is moved onto left of pivot and elements
greater than pivot are moved onto its right. This sorting technique swaps the
elements even if they are equal, hence is considered as an unstable algorithm.
PARTITION (A, p, r)
          x ← A[(p + r) / 2]
          i←p–1
          j←r+1
          while TRUE
              do repeat j ← j – 1
                    until A[j] ≤ x
              repeat i ← i + 1
                    until A[i] ≥ x
              if i < j
                    then exchange A[i] ⇔ A[j]
                    else return j
Quick Sort calls the partition subroutine to obtain the pivot element and recur-
sively call itself to sort elements from pth element to pivot and then from pivot
to rth element. This recursive call is done until p < r.
QUICKSORT (A, p, r)
          if p < r
              then q ← PARTITION(A, p, r)
                    QUICKSORT(A, p, q)
                    QUICKSORT(A, q+1, r)
     The steps for sorting of an input is given below :-
(4 2 3 5 1)→ (1 2 3 5 4)→ (1 2 3 5 4)→ (1 2 3 5 4)→ (1 2 3 5 4)→ (1 2 3 5 4)→
(1 2 3 5 4)→ (1 2 3 4 5)→ (1 2 3 4 5)→ (1 2 3 4 5)→ (1 2 3 4 5)
4.1      Worst Case
The Worst case happens when the elements are already sorted. The partition
routine returns the value as i+1. Thus the quicksort has to call partition n
times and there is a loop of n times inside the partition.Thus the order of the
quickSort becomes
T(N) = T(N-1) + O(N)
T(N) = O(N2 )
                                          8



                   Figure 4: Plot for Quick Sort Worst Case
4.2    Best Case
The Best case is when the partiton function returns the middle element. when
this happens, the array is split into half and N reduces by half every time. Thus
in the best case, We get the time of QuickSort as
T(N) = ≤ 2T(n/2) + O(n) T(N) = O(n lg n)
                                          9



                    Figure 5: Plot for Quick Sort Best Case
                         Figure 6: Comparing All Sorts
   Comparing all the sorts—Bubble, Selection, Heap and Quick, there was huge
difference in order of time.
                                       10



References
[1] Cormen, Thomas H et al, 2005, Introduction to Algorithms—Second Edi-
    tion, Prentice-Hall of India.
[2] Levitin, Anany, 2003, Introduction to The Design & Analysis of Algo-
    rithms, Pearson Education
    LATEX Reference                                
[3] LESLIE LAMPORT, 1985, LATEX—A Document Preparation System—
    User’s Guide And Reference Manual,Addison-Wesley, Reading.
[4] LATEX Tutorials, 2003, A Primer—Indian TEX Users Group, India.
[5] Greenberg, Harvey J, 1999, A Simplified Introduction to LATEX , Denver.
[6] Internet Sources
                                    11

My recent work... Query Processor

Free Downloads - VTU Engineering Works, Download the Query Processing Software for free here.  Do put on a comment to start downloading.

Get your querying done using the Query Processor, a front end for MySql.  Put on a comment to get a free copy of it.

 Screenshot of the Query Processor

VTU - Part C - Finite Automata and Formal Languages - FAFL - VTU Computer Science and Engineering

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
and also at  : http://tvvikram.blogspot.com

Contents
1 APPLICATION OF FINITE AUTOMATA                                              2
   1.1 Transducers . . . . . . . . . . . . . . . . . . . . . . . .  . . . .   2
       1.1.1 Moore machine . . . . . . . . . . . .     . . . . . .  . . . .   2
       1.1.2 Mealy machine . . . . . . . . . . . .     . . . . . .  . . . .   2
   1.2 UML state machines . . . . . . . . . . . . .    . . . . . .  . . . .   3
   1.3 Acceptors and recognizers . . . . . . . . . .   . . . . . .  . . . .   3
   1.4 Hardware applications . . . . . . . . . . . .   . . . . . .  . . . .   5
   1.5 A DFA-based Text Filter in Java . . . . . .     . . . . . .  . . . .   5
   1.6 Real-life application of Finite Automata: . .   . . . . . .  . . . .   7
2 CONTEXT FREE GRAMMAR FOR C LANGUAGE                                        12
   2.1 Grammar for ’if-else’ structure . . . . . . . . . . . . . . .  . . .  12
   2.2 Grammar for Looping Constructs . . . . . . . . . . . . .       . . .  13
       2.2.1 for loop . . . . . . . . . . . . . . . . . . . . . . .   . . .  13
       2.2.2 while loop . . . . . . . . . . . . . . . . . . . . . .   . . .  13
   2.3 Grammar for Function . . . . . . . . . . . . . . . . . . .     . . .  13
                                     1



1     APPLICATION OF FINITE AUTOMATA
1.1     Transducers
   Transducers generate output based on a given input and/or a state using
actions. They are used for control applications and in the field of computa-
tional linguistics. Here two types are distinguished:
1.1.1    Moore machine
   The FSM uses only entry actions, i.e. output depends only on the state.
The advantage of the Moore model is a simplification of the behaviour. Con-
sider an elevator door. The state machine recognizes two commands ”com-
mand open” and ”command close” which trigger state changes. The entry
action (E:) in state ”Opening” starts a motor opening the door, the entry
action in state ”Closing” starts a motor in the other direction closing the
door. States ”Opened” and ”Closed” don’t perform any actions. They sig-
nal to the outside world (e.g., to other state machines) the situation: ”door
is open” or ”door is closed”.
1.1.2    Mealy machine
   The FSM uses only input actions, i.e., output depends on input and state.
The use of a Mealy FSM leads often to a reduction of the number of states.
The example in figure 4 shows a Mealy FSM implementing the same be-
haviour as in the Moore example (the behaviour depends on the implemented
FSM execution model and will work, e.g., for virtual FSM but not for event
driven FSM). There are two input actions (I:): ”start motor to close the door
if command close arrives” and ”start motor in the other direction to open the
door if command open arrives”. The ”opening” and ”closing” intermediate
states are not shown.
   A further distinction is between deterministic (DFA) and non-deterministic
(NDFA, GNFA) automata. In deterministic automata, for each state there is
exactly one transition for each possible input. In non-deterministic automata,
there can be none, one, or more than one transition from a given state for
                                        2



              Figure 1: Transducer FSM: Mealy model example
a given possible input. This distinction is relevant in practice, but not in
theory, as there exists an algorithm which can transform any NDFA into an
equivalent but much more complex DFA.
   The FSM with only one state is called a combinatorial FSM and uses only
input actions. This concept is useful in cases where a number of FSM are
required to work together, and where it is convenient to consider a purely
combinatorial part as a form of FSM to suit the design tools.
1.2     UML state machines
   The Unified Modeling Language has a very rich semantics and notation
for describing state machines. UML state machines overcome the limitations
of traditional finite state machines while retaining their main benefits. UML
state machines introduce the new concepts of hierarchically nested states
and orthogonal regions, while extending the notion of actions. UML state
machines have the characteristics of both Mealy machines and Moore ma-
chines. They support actions that depend on both the state of the system
and the triggering event, as in Mealy machines, as well as entry and exit ac-
tions, which are associated with states rather than transitions, as in Moore
machines.
1.3     Acceptors and recognizers
   Acceptors and recognizers (also sequence detectors) produce a binary out-
put, saying either yes or no to answer whether the input is accepted by the
machine or not. All states of the FSM are said to be either accepting or not
accepting. At the time when all input is processed, if the current state is an
                                      3



           Figure 2: UML state machine example (a toaster oven)
accepting state, the input is accepted; otherwise it is rejected. As a rule the
input are symbols (characters); actions are not used. The example in figure
2 shows a finite state machine which accepts the word ”nice”. In this FSM
the only accepting state is number 7.
   The machine can also be described as defining a language, which would
contain every word accepted by the machine but none of the rejected ones;
we say then that the language is accepted by the machine. By definition, the
languages accepted by FSMs are the regular languages - that is, a language
is regular if there is some FSM that accepts it.
Start state
The start state is usually shown drawn with an arrow ”pointing at it from
any where”
Accept state
An accept state (sometimes referred to as an accepting state) is a state at
which the machine has successfully performed its procedure. It is usually
represented by a double circle.
An example of an accepting state appears on the right in this diagram of
a deterministic finite automaton (DFA) which determines if the binary input
contains an even number of 0s.
S1 (which is also the start state) indicates the state at which an even num-
ber of 0s has been input and is therefore defined as an accepting state. This
machine will give a correct end state if the binary number contains an even
number of zeros including a string with no zeros. Examples of strings ac-
cepted by this DFA are epsilon (the empty string), 1, 11, 11..., 00, 010, 1010,
10110 and so on.
                                       4



              Figure 3: Acceptor FSM: parsing the word ”nice”
1.4     Hardware applications
   In a digital circuit, an FSM may be built using a programmable logic
device, a programmable logic controller, logic gates and flip flops or relays.
More specifically, a hardware implementation requires a register to store state
variables, a block of combinational logic which determines the state transi-
tion, and a second block of combinational logic that determines the output
of an FSM. One of the classic hardware implementations is the Richards
controller.
   Mealy and Moore machines produce logic with asynchronous output, be-
cause there is a propagation delay between the flip-flop and output. This
causes slower operating frequencies in FSM. A Mealy or Moore machine can
be convertable to a FSM which output is directly from a flip-flop, which
makes the FSM run at higher frequencies. This kind of FSM is sometimes
called Medvedev FSM. A counter is the simplest form of this kind of FSM.
1.5     A DFA-based Text Filter in Java
The first thing to deal with is the input alphabet. The DFA above uses the
alphabet 0, 1, which is the alphabet of interest for this problem. But the
program will work with a typed input string, so we do not have the luxury
of restricting the alphabet in this way. The program should accept ”011” (a
representation for the number 3) and reject ”101” (a representation for the
number 5), but it must also properly reject strings like ”01i” and ”fred”. The
                                       5



alphabet for the Java implementation must be the whole set of characters
that can occur in a Java stringthat is, the whole set of values making up the
Java char type. The DFA we actually implement will have four states, like
this:
    An object of the Mod3 class represents such a DFA. A Mod3 object has
a current state, which is encoded using the integers 0 through 3. The class
definition begins like this:
/**
  A deterministic finite-state automaton that
 recognizes strings that are binary representations
  of natural numbers that are divisible
  by 3. Leading zeros are permitted, and the
  empty string is taken as a representation for 0
  (along with ”0”, ”00”, and so on).
 /
public class Mod3
/
  Constants q0 through q3 represent states, and
  a private int holds the current state code.
 /
private static final int q0 = 0;
private static final int q1 = 1;
private static final int q2 = 2;
private static final int q3 = 3;
                                       6



private int state;
The int variables q0, q1, q2, and q3 are private (visible only in this class),
static (shared by all objects of this class), and final (not permitted to change
after initialization).
1.6     Real-life application of Finite Automata:
Introduction:
In future communication scenarios, mobile devices with multiple wireless in-
terfaces will be able to seamlessly roam around, hoping from a network to an-
other (and using different technologies) without losing their IP connection. A
combination of technologies which includes Local Area Networks (WLANs),
Wireless Personal Area Networks (PANs), Cellular Networks (GSM, GPRS,
UTMS) and Community Area Networks (WiMax, 802.11) will provide the
infrastructure needed for this environment. Handovers can happen between
2 domains using the same technology (horizontal handover) or from different
technologies (vertical handover). Such a rich environment could bring up a
new world of business possibilities and the proposal described here tries to
create the proper conditions to exploit those innovations.
              Figure 4: A heterogeneous mobile overlay network[1]
                                         7



    Uses of the Platform
1. From the network management perspective (the access provider):
• It may be interested on grabbing usual information which would be inter-
esting to improve long term relationship with the user;
• It may collect information about the handovers of a user and relate them
with positioning information;
• It may correlate information about routes and timing of accesses.
2. From the content provider perspective:
• It may adapt the delivery of media to specifics of devices, location, timing,
type of user, etc
• It can understand the criteria by which the user chooses the access providers;
• It can explore the contextual information to add value to the content (ad-
vertisement, linking to 3rd party products, etc);
• As the user has the control over the mobility aspects, the access provider
can focus on providing better and more varied services[4];
• It can provide brokerage services based on the common information avail-
able.
3. From the user perspective:
• It can choose the provider based upon several criteria:
• Best price
• Better response
• Best matching to his/her requirements
• Economy (use a home user-owned WLAN, during a traffic jam)
• It can use contextual information to adapt the user device profile of usage:
• Power management (CPU, memory, display, network interface)
• Streaming control (proximity to known blind spots such as tunnels)
• Optimization of content delivery to a new profile, on vertical handovers
with a lower bandwidth provider.
    The Relationship with PROTON
A Mobile IPv6 environment, connected to a Vodafones GPRS network, has
been set up at the Computer Laboratory of the University of Cambridge in an
effort to demonstrate a 4G mobile scenario[1]. The main aims for the testbed
were to assess the performance issues involved in the wireless overlays in a
heterogeneous environment and to improve the seamlessly capabilities of the
handover process. Figure 2 shows the system implemented at the Computer
Lab.
    The structure of the Ontology
A service is a facility (a video streamer, a voice channel or a game applica-
tion) which a content provider offers, during a session, to a user through an
                                       8



access provider. One entity can offer both access and content at the same
time. Context and Handover information, gathered by positioning sensors
and other sources from the user device or by any other related service, can be
used both by the session to frame Security, Privacy, QoS and other policies.
    SLA is signed between all the entities involved in order to offer to the user
some parameters by which they can measure his/her Quality of Experience
while using the system Figure 4.
This ontology will allow for:
• The creation of a common vocabulary of terms which would easy the de-
sign and reuse in new services in the communications industry, with faster
deployment and exploration in the added value chain;
• Definition of complex relationships between the terms which would make
possible to correlate the business processes, exploring new possibilities de-
rived from the positioning and context awareness technologies as well as from
security/privacy policies;
• A structured integration of the Access Networks, Subscriber Profiles, Ap-
plications and Data both by a provider, or by a group of providers;
• Other ontologies in the IT management domain can be imported, increas-
ing the management boundaries.
                                       9



      Figure 5: The archtecture and relationship between the entities
   Each provider will have its own policies about IT Management. Some of
these policies can be shared between providers to deliver ubiquitous services,
and others can be protected or hidden for business reasons.
    Methodology and adherence to standards
We have particular preoccupation on following established or emerging stan-
dards in the implementation of this project. SOUPA Core defines wide range
terms and relationships that are of general use for different ubiquitous appli-
cations. SOUPA Extension defines vocabularies for specific types of applica-
tions. We understand that, for this platform, the core ontology will take care
of the common vocabulary which will be used by all the entities belonging to
the environment. The overall methodology which will be used for ontology
development is the Methontology[8].
   The ontology will be described in OWL[9] (Web Ontology Language),
which is the prime language created for the Semantic Web. OWL is incor-
porated on the Protg tool[10], which is a good platform to design ontologies.
The Jena API[11] is used by Protg-OWL for various tasks during the devel-
opment and prototyping of the ontology and its applications.
                                      10



             Figure 6: Structure of Wireless MIPv6 Testbed [5]
   In this model, the activities can be set as having technical meaning (the
updating of a table in a database) or a business meaning (the update of
a customer address). SOA-based applications make available interfaces for
other applications via service components. Through the pipelining of multi-
ple components via request/reply remote calls more complex composite ap-
plications, a logical module in a larger business model, can be constructed.
Another model, the Event Driven Architecture (EDA)[13], defines a model
of developing application components which exchange events to implement
business functions. There are long arguments about the preferences on us-
ing SOA or EDA model, or if any of them should provide the right paradigm.
   The environment has been installed composed by APs from CISCO, 4
PDAs from HP (5550), 2 notebooks, 3 GPSs, 2 Switches 3COM and 4 Desk-
tops. Linux have been used on the notebooks and windows on the PDAs.
    Source: Internet
                                      11



2     CONTEXT FREE GRAMMAR FOR C LAN-
      GUAGE
A context free grammar(CFG)[is sometime called Backus-Naur Form(BNF)]
is a tuple where:
a. T is a set of terminals
b. N is a set of non-terminals
c. S is the start symbol in N
d. P is a set of production of the form
2.1     Grammar for ’if-else’ structure
The grammar is: ifthen — ifthenelse
Consider the following grammar describing if/then/else statements:
S → if E then S
S → if E then S else S
S → other
”other” just means some other kind of statement that is not an if/then/else
statement. Now consider input of the form if e1 then if e2 then s1 else
s2. The grammar is ambiguous because there are two possible parse trees
for the input.
Consider the following derivations of the input:
Derivation 1 - Leftmost Derivation
S S → if E then S
if E then S S →if E then S else S
if E then if E then S else S
Derivation 2 - Rightmost Derivation
S S → if E then S else S
if E then S else S S → if E then S
if E then if E then S else S
Generally, the first parse tree is the one we want, an else should always be
matched with the closest unmatched then. It could be as:
S→M
S→O
M → if E then M else M
M → other
O → if E then S
O → if E then M else O
The M nonterminal means a ”matched” statement in which there are no oc-
                                      12



currences of then that are not matched by an else.
M = {V, T, X, P}
V = {S, X, C, I}
T = {e, c}
X → CSES|ICS
S → S|CS|
C → e|c
e → any valid arithmetic expressions
c → comparision statements
2.2     Grammar for Looping Constructs
2.2.1   for loop
M = {V, T, initial, P }
V = {loop, initialization, condition, increment}
T = {alphabets, numbers, variables}
loop → intialization condition increment statements
intialization → variable = number
condition → expressions comparison
increment → increment decrement
statements → S|
variable → alphabets | alphabets number
alphabets → a − zA − Z
2.2.2   while loop
M = {V, T, R, P }
V = {W, R, S}
T={}
R → W CS        ;means ”while condition statement”
S → validcstatements
2.3     Grammar for Function
M = {V, T, F, P}
V = {F,return,FN,argument list}
T = {alphabets,void,int,char,double}
F → return F N argumentlist
                                       13
return → void|int|double|char
F N → alphabets
alphabets → [a to z]|[a − z0 − 9]
argumentlist → declaration of f ormal variables
body → [ valid c statements]
   Source: Internet
                                   14

VTU - Part B - Finite Automata and Formal Languages - FAFL - VTU Computer Science and Engineering

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
and also at  : http://tvvikram.blogspot.com
Contents
1 Formal languages                                                           2
   1.1 For the English Language: . . . . . . . . .    . . . . . .  . . . . . 2
   1.2 Finite-State Grammars . . . . . . . . . . .    . . . . . .  . . . . . 2
   1.3 The general form of finite state grammars       . . . . . .  . . . . . 3
   1.4 The Chomsky Hierarchy . . . . . . . . . .      . . . . . .  . . . . . 4
2 Different Proving Techniques                                                5
   2.1 Mathematical Induction . .     . . . . . . . . . . . . . .  . . . . . 5
       2.1.1 Description . . . . .    . . . . . . . . . . . . . .  . . . . . 5
   2.2 Contradiction . . . . . . . .  . . . . . . . . . . . . . .  . . . . . 6
       2.2.1 Example: . . . . . .     . . . . . . . . . . . . . .  . . . . . 6
   2.3 Deduction . . . . . . . . . .  . . . . . . . . . . . . . .  . . . . . 7
       2.3.1 Deduction Logic . . .    . . . . . . . . . . . . . .  . . . . . 7
3 Automata of an Automated Teller Machine - ATM                              9
                                     1


Formalization of natural languages using formal structure
1     Formal languages
  In formal language theory, a language is a set of strings. A string is just a
sequence of symbols chosen from an agreed-upon set of symbols, called the
vocabulary or lexicon.
1.1     For the English Language:
  • Any sequence of English words from the Oxford English Dictionary like
what a language!, books written knowledge people are examples whereas We
sdf hit iflas bgow sil will not make English a formal language.
  • Strings over {a, b, c} starting with a like abbb, a, a followed by a million
bs is an example whereas bcacc, the zero-length string epsilon.
  • Strings over {a, b, c, d} in alphabetical order like abd, ad, bcd, b, abcd
are examples whereas dbcd, ba.
  All the examples are defined with rules given before each example. The
idea of generative grammar is to use grammars to define a set that closely
resembles a natural language for instance, all and only the acceptable English
sentences. However, not all sets are definable by all types of grammars. We
require a set of rules to accurately describe a natural language.
1.2     Finite-State Grammars
To generate strings over {a, b, c, d} in alphabetical order, let S be the start
symbol of the grammar.
S → a S1
S → b S2
S → c S3
S→d
S1 → b S2
S1 → c S3
S1 → d
S2 → c S3
S2 → d
S3 → d
                                       2



    Grammar has a corresponding finite state machine that recognizes all and
only the sentences it generates.
1.3        The general form of finite state grammars
Any grammar having only rules of the form A → bC where A,B are nonter-
minals and b is a terminal has a corresponding finite state machine. Given
a string, if a path can be found through the machine, the string is generated
by the grammar and vice versa. There are some languages that cannot be
recognized by finite state machines.
      Sequence of as followed by an equal number of bs like ab, aabb, aaabbb,
. . . is an example whereas aabbb, aaaaaaaaaaaabbb do not form the grammer
as per the rule.
      Call the number of as in the sentence being analyzed n. A finite state
machine would need to remember this number n while waiting for the end
of the bs. But, by definition, a finite state machine will only have enough
states to remember some fixed number of as. Hence there exists neither a
finite-state grammar nor a finite state machine for the language an bn .
English is just like an bn
Consider
a. The cat died.
b. The cat the dog chased died.
c. The cat the dog the rat bit chased died.
d. The cat the dog the rat the elephant admired bit chased died
...
f A = {the cat, the dog, the rat, the elephant, the kangaroo, . . .} and
B = {chased, bit, admired, ate, befriended, . . .} its clear that it has the
structure an bn died.
    Chomsky and Miller (1963) argued that the obligatory paired dependen-
cies presented by either. . .or, if. . .then or the agreement between verbs and
subjects can nest inside one another to an arbitrary depth.
    The following grammar does not generate the language an bn . It is a
context-free grammar, and as such is capable of deriving any number of
center-embeddings.
S→ab
S→aSb
                                           3



1.4     The Chomsky Hierarchy
   Let A,B be nonterminals, b a terminal, alpha nonempty sequence of either
kind of symbol, and , γ, δ possibly empty sequences of either kind of symbol.
The Chomsky Hierarchy is a classification of languages in a subset relation-
ship. Each language has corresponding class of machine that recognizes it.
  language attribute         rule type       machine
                             A →bC
  finite-state                                finite state machine
                             A→α
  context-free                               push down automata
                             γ A δ → γαδ
  context-sensitive                          linear bounded
  automation unrestricted no restrictin      Turing machine
   The cardinality of the set of languages definable by a grammar formalism
is called its generative capacity.
Natural languages are believed to reside somewhere between context-free and
context-sensitive.
    Source: Internet
                                       4



2      Different Proving Techniques
2.1      Mathematical Induction
Mathematical induction is a method of mathematical proof typically used to
establish that a given statement is true of all natural numbers. It is done
by proving that the first statement in the infinite sequence of statements is
true, and then proving that if any one statement in the infinite sequence of
statements is true, then so is the next one.
     The method can be extended to prove statements about more general
well-founded structures, such as trees; this generalization, known as struc-
tural induction, is used in mathematical logic and computer science. Math-
ematical induction in this extended sense is closely related to recursion.
2.1.1     Description
The simplest and most common form of mathematical induction proves that
a statement involving a natural number n holds for all values of n. The proof
consists of two steps:
     1. The basis (base case): showing that the statement holds when n = 0
or n = 1.
2. The inductive step: showing that if the statement holds for some n, then
the statement also holds when n + 1 is substituted for n.
     The assumption in the inductive step that the statement holds for some
n is called the induction hypothesis (or inductive hypothesis). To perform
the inductive step, one assumes the induction hypothesis and then uses this
assumption to prove the statement for n + 1.
     The description above of the basis applies when 0 is considered a natural
number, as is common in the fields of combinatorics and mathematical logic.
If, on the other hand, 1 is taken to be the first natural number, then the base
case is given by n = 1.
     This method works by first proving the statement is true for a starting
value, and then proving that the process used to go from one value to the
next is valid. If these are both proven, then any value can be obtained by
performing the process repeatedly. It may be helpful to think of the domino
effect; if one is presented with a long row of dominoes standing on end, one
can be sure that:
1. The first domino will fall.
2. Whenever a domino falls, its next neighbour will also fall.
     So it is concluded that all of the dominoes will fall, and that this fact is
inevitable.
                                        5



2.2     Contradiction
In logic, proof by contradiction is a form of proof that establishes the truth
or validity of a proposition by showing that the premise that the proposition
is false implies a contradiction. Since by the law of bivalence a proposition
must be either true or false, and its falsity has been shown impossible, the
proposition must be true.
    In other words, to prove by contradiction that P, show that ¬ P ⇒⊥ or
its equivalent ¬ P ⇒ (Q ∧ ¬ Q). Then, since ¬ P implies a contradiction,
conclude P.
    Proof by contradiction is also known as indirect proof, apagogical argu-
ment, reductio ad impossibile, or reductio ad absurdum.
    In a proof by contradiction we assume, along with the hypotheses, the
logical negation of the result we wish to prove, and then reach some kind of
contradiction. That is, if we want to prove ”If P, Then Q”, we assume P and
Not Q. The contradiction we arrive at could be some conclusion contradicting
one of our assumptions, or something obviously untrue like 1 = 0.
2.2.1     Example:
A classic proof by contradiction from Greek mathematics is the proof that
the square root of 2 is irrational. If it were rational, it could be expressed
as a fraction a/b in lowest terms, where a and b are integers, at least one of
                              √
which is odd. But if a/b = 2, then a2 = 2b2 . Therefore a2 must be even.
Because the square of an odd number is odd, that in turn implies that a is
even. This means that b must be odd because a/b is in lowest terms.
    On the other hand, if a is even, then a2 is a multiple of 4. If a2 is a
multiple of 4 and a2 = 2b2 , then 2b2 is a multiple of 4, and therefore b2 is
even, and so is b.
    So b is odd and even, a contradiction. Therefore the initial assumption-
      √
that 2 can be expressed as a fractionmust be false. One of the first proofs
by contradiction is the following gem attributed to Euclid.
Theorem: There are infinitely many prime numbers.
    Proof : Assume to the contrary that there are only finitely many prime
numbers, and all of them are listed as follows:
p1, p2 ..., pn. Consider the number q = p1p2... pn + 1.The number q is
either prime or composite. If we divide any of the listed primes pi into q,
this would result in a remainder of 1 for each i = 1, 2, ..., n. Thus, q cannot
be composite.
    We conclude that q is a prime number, not among the primes listed above,
                                       6



contradicting our assumption that all primes are in the list p1, p2 ..., pn.
Proof by contradiction is often used when we wish to prove the impossibility
of something.
2.3     Deduction
In logic, natural deduction is an approach to proof theory that attempts to
provide a deductive system which is a formal model of logical reasoning as it
”naturally” occurs. This approach is in contrast to axiomatic systems which
use axioms.
2.3.1    Deduction Logic
The nine primitive rules
        1. The Rule of Assumption (A)
        2. Modus Ponendo Ponens (MPP)
        3. The Rule of Double Negation (DN)
        4. The Rule of Conditional Proof (CP)
        5. The Rule of -introduction (I)
        6. The Rule of -elimination (E)
        7. The Rule of -introduction (I)
        8. The Rule of -elimination (E)
        9. Reductio Ad Absurdum (RAA)
    In system L, a proof has a definition with the following conditions:
1. has a finite sequence of well-formed formulas (or wffs)
2. each line of it is justified by a rule of the system L
3. the last line of the proof is what is intended, and this last line of the proof
uses only the premises which were given, if any.
    An example of the proof of a sequent
p → q, ¬q ¬p [Modus Tollendo Tollens (MTT)]
                                         7
  Assumption number     Line number     Formula (wff) Lines in-use and Justification
           1                 (1)            (p→q)                    A
                                              ¬q
           2                 (2)                                     A
           3                 (3)               p               A(For RAA)
          1,3                (4)               q                 1,3,MPP
                                            q∧ ¬q
         1,2,3               (5)                                    2,4
                                              ¬p
          1,2                (6)                                 3,5,RAA
                                            Q.E.D
A deduction (or proof) can be defined precisely in the context of a formal
system like the propositional calculus. A proposition is deduced from a col-
lection of premises by applying inference rules repeatedly. The deduction is
a record of this repeated application of inference rules.
    Source: Internet
                                      8




        3      Automata of an Automated Teller
                               Machine - ATM
An Automated Teller Machine is one of the automata thats too common in
real life. It follows the following automata to validate the card and execute
the transaction.
• It accepts the card.
• Validates the card with the server. The server authorises the card.
• If the card is invalid, it enters the trap state.
• On succesful validation of the card, it asks for the user to input the secret
PIN provided.
     User Inputs PIN. The PIN’s validity is matched with the card from the
server.
• Ater the PIN is accepted and the card is found to be valid, and thus the
user is valid, it asks for the transaction to happen.
    In case of withdrawal it asks for amount to withdraw. Checks for suffi-
cient balance and if user doesnot have, it aborts the transaction.
    Otherwise the amount is deducted from user’s account database. The
amount is handed over to the user and transaction is closed.
    The automata for the ATM can be represented as shown in graph.
                                         9
Figure 1: Automata of an ATM
        Source: Internet
               10

VTU - Part A - Finite Automata and Formal Languages - FAFL - VTU Computer Science and Engineering

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