Different Types of Automata in Language Theory

  It is very important for every one interested in Computer Science to understand various Automata in language theory. Often there is a big confusion about the relationship between various Automaton. There are different Automata, but the most important ones with practical applications are the following. Turing Machine (TM), Linear Bounded Automata (LBA), Push Down Automata (PDA) and Finite Automata (FA).

  Each one of theses Automata are having a Deterministic and non deterministic variant associated with them. It is often confusing since there are eight different types of Automata to account for. Here I have included simple Venn diagrams to show the hierarchy of Automata. The outer most set is the one with the most power. Here power is the ability to accept strings belonging to complicated languages. The Automata with more power can accept more complicated strings. Remember here I have used layman's terms. 

The Venn diagram given below shows a power comparison between the four types of Automata.

A hierarchy of different Automata

 Now let us see how a Deterministic Turing Machine (DTM) is related to  a Non deterministic Turing Machine (NTM). The Venn diagram given below gives an idea about the two Automata.

Turing Machine Hierarchy

   

  Next is the least known of all the four Automata. The Linear Bounded Automata (LBA). Well here we don't have a clear answer about the relationship between a Deterministic LBA (DLBA) and a Non deterministic LBA (NLBA). It is still an unsolved problem in Computer Science. So I give a Venn diagram showing both the possibilities.

Here is an Open Problem. You could give it a try.

  Now we have Push Down Automata (PDA). The relationship between Deterministic PDA (DPDA) and Non deterministic PDA (NPDA) is shown in the Venn diagram given below.

DPDA and NPDA are having different powers

  

  Finally we have Finite Automata. Both Non deterministic Finite Automata (NFA) and Deterministic Finite Automata (DFA) are having equal powers. The Venn diagram below shows their relationship.

NFA and DFA

  The last figure given below shows the relationship between various Grammars associated with the above mentioned Automaton.

Hierarchy of Grammars

Beamer Template for Simple Presentations.

  Research communities all over the world prefers presentations created using Latex. But most of us still use prefer Proprietary software like MS Word. The main reason for such preferences is not often the ignorance regarding open source alternatives. Many of us are simply afraid of working with a new technology, especially if it involves a few commands. 

  LATEX is a very good document preparation tool. Once you create a few documents using LATEX you will enjoy working with it. To create presentations LATEX provides a class called Beamer. Here I have included a Template for creating simple presentations. I have also included a presentation in PDF format which was created by running the program with Beamer Theme "beamerthemesidebar". Please compile the Program twice. Only then you will get a correct Table of Contents listing.

Click here to download the Tex Program for creating simple presentations.

Click here to download the Presentation in PDF format obtained after running the program with Beamer theme sidebar.

Latex Template for IEEE Conference Papers

   

  It is difficult to produce quality results in research. But some times it is even more difficult to produce a good quality IEEE Format paper. You have to worry about the font styles, alignment, margins and what not if you are using MS Word or some such word processor. If you are using Latex often you have to worry about different commands and packages. So here I try provide a simple LATEX Template for creating IEEE Conference Papers. I have tried to make it as simple as possible, and I have also given sufficient comments where ever required. Here I give two links the first one is to the tex file which you need to run in Texmaker. If you want you can also download the pdf file you will get when you run the tex file without making any modifications.



Click here to download the Tex file which gives a Template for creating IEEE Conference Papers.
 

Click here to download the PDF file generated, if you run the Tex file without any modification.

Function Pointers in C

//Program illustrates how function pointers are used to call various functions.

#include<stdio.h>
void apple(int x[3])
{
  int i;
  printf("\n From Function apple\n");
  for(i=0;i<3;i++)
  {
      printf("%d\t",x[i]);
  }
}

void ball(int x[3])
{
  int i;
  printf("\n From Function ball\n");
  for(i=0;i<3;i++)
  {
      printf("%d\t",x[i]);
  }
}

void cat(int x[3],void (*fp1)(int [3]))
{ 
/*cat is a function which receives a 1 Dimensional integer array and a function pointer as arguments*/
 
      printf("\n\n From function cat\n");
      (*fp1) (x);      /*Calling function pointed by function pointer fp1 with array x as argument*/
}

int main()
{

 int arr1[3]={111,222,333};
 int arr2[3]={444,555,666};

 void (*e[2]) (int [3]);
 /* 2 Function Pointers e[0] and e[1] which can point to a function with
     one Dimensional integer array as argument and returns void          */

  void (*fp) (int [3], void (*e) (int [3]) );
 /* Function Pointer fp which can point to a function with
     one Dimensional integer array and function pointer as arguments and returns void        */

   e[0]=apple;              /*function pointer e[0] points to function apple*/
   e[1]=ball;                 /*function pointer e[1] points to function ball   */
   fp=cat;                     /*function pointer fp points to function cat       */

   (*e[0]) (arr1);          /*caling function apple with array arr1 as argument*/
   (*e[1]) (arr2);          /*caling function ball with array arr2 as argument   */

   (*fp) (arr1,e[0]);      /*caling function cat with array arr1 and function pointer e[0] as arguments */
   (*fp) (arr2,e[1]);      /*caling function cat with array arr2 and function pointer e[1] as arguments */
   (*fp) (arr1,apple);
    /*caling function cat with array arr1 and function pointer using function name apple as arguments */
   (*fp) (arr2,ball);
    /*caling function cat with array arr2 and function pointer using function name ball as arguments    */
    return 0;
}

Click here to down load the C Program. 

Generic Classes in C++

//Program illustrates the working of generic classes in C++.
#include<iostream>
#include<fstream>
using namespace std;

template <class x,class y> void swap(x *a,y *b)
{
    x temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

int main()
{
    int n1=10,n2=20;
    float f1=11.11,f2=22.22;
    cout<<"\nn1 is: "<<n1<<"\nn2 is: "<<n2;
    cout<<"\nf1 is: "<<f1<<"\nn2 is: "<<f2;
    swap(&n1,&n2);
    swap(&f1,&f2);
    cout<<"\nn1 is: "<<n1<<"\nn2 is: "<<n2;
    cout<<"\nf1 is: "<<f1<<"\nn2 is: "<<f2;
    return 0;
}


Click here to download the C++ Program.

Program illustrating Reinterpret Cast in C++

//Program illustrates the working of reinterpret_cast keyword in C++
#include<iostream>
#include<typeinfo>
using namespace std;

int main()
{

    char *s="Hello Friends";
    int i;

    i=reinterpret_cast<int>(s);
    cout<<"\ni is: "<<i;
    cout<<"\ns is: "<<s;

    return 0;
}

Click here to download the C++ Program.

Program illustrating Static Cast in C++

//This Program illustrates how static_cast keyword is used in C++
#include<iostream>
#include<typeinfo>
using namespace std;

int main()
{

    int i;
    const int x=100;
    i=static_cast<int>(x);
    cout<<"\ni is: "<<i;

    return 0;
 }


Click here to download the C++ Program

Program illustrating Dynamic Cast in C++

//Program illustrates how dynamic_cast keyword in C++ is used

#include<iostream>
#include<typeinfo>
using namespace std;

class a
{
    public:
    virtual void show()=0;
};
class b : public a
{
    public:
    void show()
    {
        cout<<"\nshow() in class B\n";
    }
};
class c : public a
{
    public:
    void show()
    {
        cout<<"\nshow() in class C\n";
    }
};
class d : public a
{

   public:
   void show()
    {
        cout<<"\nshow() in class D\n";
    }
};
int main()
{
    int i,j;
    b b1,b2;
    c c1;
    d d1;
    a *a1[4]={&b1,&c1,&d1,&b2};

    for(i=0;i<4;i++)
    {
        b *b3=dynamic_cast<b *>(a1[i]);
        if(b3)
        {
            cout<<"\nFrom B\n" ;
            b3->show();
        }
        else
        {
            cout<<"\nNot From B\n";
            cout<<"a1["<<i+1<<"] is pointing to"<<typeid(*a1[i]).name()<<"\n";
            a1[i]->show();
        }

    }

    return 0;
}

Click here to download the C++ Program.

Program illustrating Namespaces in C++

//The following programs illustrates namespaces in C++
//Compare the syntax of the three Programs you will understand the scope of namespaces in C++
//Program 1 begins here.

#include<iostream>
#include<typeinfo>
using namespace std;
namespace{
    int i=444;
}
namespace ns1
{

int j=555;
namespace ns2
{
    int k=666;
}
}

int main()
{
    cout<<"\ni is: "<<i;
    cout<<"\nj is: "<<ns1::j;
    cout<<"\nk is: "<<ns1::ns2::k;
    return 0;
}

//Program 2 Begins here.
#include<iostream>
#include<typeinfo>
using namespace std;
namespace{
    int i=444;
}
namespace ns1
{

int j=555;
namespace ns2
{
    int k=666;
}
}
using namespace ns1;
using namespace ns1::ns2;
int main()
{
    cout<<"\ni is: "<<i;
    cout<<"\nj is: "<<j;
    cout<<"\nk is: "<<k;
    return 0;
}

//Program3 begins here.
#include<iostream>
#include<typeinfo>
using namespace std;
namespace{
    int i=444;
}
namespace ns1
{

int j=555;
namespace ns2
{
    int k=666;
}
}

using namespace ns1::ns2;
int main()
{
    cout<<"\ni is: "<<i;
    cout<<"\nj is: "<<ns1::j;
    cout<<"\nk is: "<<k;
    return 0;
}

Click below to download the C++ Programs.

• Program 1. 
• Program 2. 
• Program 3.

Why we must support Distributed Computing Projects?

 

When I had a chat with some of my friends recently, I had a shocking revelation. Not many of us are familiar with distributed computing projects. What is a distributed computing project and why we must support them?
 
Well a distributed computing project tries to solve a big problem by dividing it into a number of small sub problems and then by solving and combining the sub problem we will get a solution for the first problem. Some of the problems can be easily divided into sub problems for solution. Consider the problem of finding the factors of a very large number. The problem can be solved using a large number of computers by assigning each computer with a range of values to check whether it can be a factor of the given large number.

Some of the practical problems need a very large amount of computing power. So one solution is to divide the problem into a large set of sub problems each of which can be solved by personal computers or laptops without much power. There are hundreds of distributed computing projects in need of our computing resources which are freely available and often under utilized. All we need to do is go to a particular projects home page and download the program. Most of the programs are very small in size. They will run automatically in your computer and once in a while they will communicate with the server to send back the results and get new assignments.There are no hidden viruses or trojans and with a single click you can uninstall the programs.

The two projects I run on my computer are The Great Internet Mersenne Prime Search (GIMPS) and Folding@home (FAH or F@h).

GIMPS tries to identify large Mersenne prime. A clear understanding of Mersenne primes will help us develop better cryptographic algorithms.

The Links to the wikipedia article on GIMPS and GIMPS Home page are given below.

Wikipedia Article on GIMPS
GIMPS Home Page


FAH is a project for disease research that simulates protein folding. The results are very useful in cancer treatment. The idle CPU in your computer can be used as an effective tool to fight cancer.


The Links to the wikipedia article on FAH and FAH Home page are given below.

Wikipedia Article on FAH
Home Page of FAH


There are other interesting distributed computing projects also. The Link to the wikipedia article is given below.

Wikipedia article on Distributed computing Projects   

If you have any suggestions or corrections please post a comment.  

Program illustrating Const Cast in C++

//The following Program illustrates the working of const_cast

#include <iostream>
using namespace std;

void print (char * str)
{
  cout<<"\nFrom Function print\n";
  cout << str;
}

int main () {
  const char * c = "Hello Friends";
  cout<<"\nFrom main Function\n";
  cout<<c;
  print ( const_cast<char *>(c) );
  return 0;
}

//The following given below is equivalent to the above Program

#include <iostream>
using namespace std;

void print (char * str)
{
  cout<<"\nFrom Function print\n";
  cout << str;
}

int main () {
  const char * c = "Hello Friends";
  cout<<"\nFrom main Function\n";
  cout<<c;
  print ( (char *)(c) );
  return 0;
}


// The Program given below will not work.

#include <iostream>
using namespace std;

void print (char * str)
{
  cout<<"\nFrom Function print\n";
  cout << str;
}

int main () {
  const char * c = "Hello Friends";
  cout<<"\nFrom main Function\n";
  cout<<c;
  print ( c );
  return 0;
}

Click here to download the C++ Program.

Xgraph for plotting in NS-2

After running your NS-2 program you will have a trace file as output.

Let us assume the name of the output file is "trace1.tr"

The trace file might look like below

+ 1             0 2 cbr 210 ------- 0 0.0 3.1 0 0
- 1              0 2 cbr 210 ------- 0 0.0 3.1 0 0
r  1.00212  0 2 cbr 210 ------- 0 0.0 3.1 0 0
+ 1.00212  0 2 cbr 210 ------- 0 0.0 3.1 0 0
+ 1.055      0 3 cbr 210 ------- 0 0.0 3.1 0 0

I am not explaining the meaning of the trace file. Instead I am giving instructions to use xgraph to draw a graph involving data extracted from the trace file.

To use xgraph we need 2 columns of data. The Unix command called "cut" is used for this purpose.

Open terminal and type the following commands

###############################

    cut  -d  " "  -f  2  trace1.tr  >  file1

    cut  -d  " "  -f  6  trace1.tr  >  file2

    paste      file1     file2    >   output

    xgraph   output

###############################

This will extract columns 2 and 6 and then draw a graph using the xgraph utility.

 
 for "cut" keyword -d specifies the delimiter between columns.
 Here the delimiter is white space ("  ").
 -f specifies the column number of the data to be extracted. 

1 D and 2 D array pointers in C

#include<stdio.h>
void main()
{
 int a[3][3]={111,222,333,444,555,666,777,888,999};
 int i,j,*p;
 int (*m)[3][3];  /* Pointer to a 2 Dimensional Array*/
 int (*n)[3];     /* Pointer to a 1 Dimensional Array*/
 p=a;
 m=a;
 n=a;

for(i=0;i<3;i++)
 {
  for(j=0;j<3;j++)
  {
   printf("%d ",*p++);
  }

 }
printf("\n");


for(i=0;i<3;i++)
 {
  for(j=0;j<3;j++)
  {
   printf("%d ",a[i][j]);
  }

 }
printf("\n");


for(i=0;i<3;i++)
 {
  for(j=0;j<3;j++)
  {
   printf("%d ",*(*(*m+i)+j));
   printf("%u \n",m+i);
  }
 }
printf("\n");

for(i=0;i<3;i++)
 {
   for(j=0;j<3;j++)
   {
     printf("%d ",*(*(n+i)+j));
     printf("%u \n",n+i);
   }
 }
}

Click here to download the C Program.

C Program to Print Enumerated Variables

#include<stdio.h>
#include<io.h>
void main()
{
 enum a{x=111,y=222,z=333};
 enum a b;
 b=z;
 printf("\nThe enum x is %d",x);
 printf("\nThe enum y is %d",y);
 printf("\nThe enumeration variable b is %d",b);
}

Click here to download the C Program.


/* You don't need typecasting to print enumerated variables. But the following Program will also work. */


#include<stdio.h>
#include<io.h>
void main()
{
 enum a{x=111,y=222,z=333};
 enum a b;
 b=z;
 printf("\nThe enum x is %d",(int)x);
 printf("\nThe enum y is %d",(int)y);
 printf("\nThe enumeration variable b is %d",(int)b);
}


Click here to download the C Program.
 

What are My Intentions?

  I have been working with computers for more than a decade and now I have some knowledge about computing. I have been relying on materials prepared by others for a very long time. When ever I was in need of some basic Programs, all I used to do was search for it in Google. So I had help from countless individuals who contributed in a selfless manner to the society. Now I believe it is my turn to return what I have received from others. So here in this Blog I try to give Programs illustrating certain features in various programming languages like C, C++, Java, Python etc.

  At a later stage I also want to include topics on tools like Matlab, NS-2 etc. Maybe if time permits I might include tips and tricks on some of my favorite Computer Science subjects like Theory of Computation, Analysis of Algorithms, Cryptography etc.

  If you find the contents useful or if you have any corrections or suggestions feel free to post a comment. Also if you have any doubts or problems please post them here. I will try to give a solution if it is within my reach.

  If you find this Blog useful please visit my other Blog titled "Let Us Fight Poverty" on which I have posted articles dealing with issues having social relevance.