What is theory of automata?

This subject is a fundamental subject and it is study to know about the compilers design, operating system, and system software. The automata theory is the base of this subject.

Theory of automata is the branch of computation theory in which we study about the abstract computing mechanisms and machines .It has been extended in many directions like modeling computation, real time and embedded systems or complexity theory. An automaton is defined as a system in which energy; information is transformed for performing some functions without the direct involvement of man. An automaton is a machine that performs computation on an input by moving through transitions from one state to another. If it is reach at accepting state then it will accept the input. These computations are used to represent various mathematic al models. There are many types of model such as finite automata, pushdown automata and Turing machine.

Why we study automata theory?

1)      Turing tell us the boundary between what an abstract machines could do and what it could not do.

2)      Stephen  Cook defines “intractable “ and NP-hard problems which can be solved easily but in practice they take so much time that computers are useless.

Finite automata:

A Finite automaton is a machine which moves on an input through transitions by moving one state to another. There are 5 tulles of finite automata represented by (Q, ∑, q0, F, δ) where

Q is the finite non empty set of states.

∑   is finite non empty set of inputs called input alphabet.

 q₀ ϵ Q is the initial state.

  F is the set of final states.

 Δ is a transition function which describes the change of states during the transition. It is also called the next state function.

Block diagram of finite automata





Description of block diagram:

1)      Input tape:  A Finite automata has an input tape. This input tape is divided into squares and each square contain a string symbol. At the rightmost and leftmost there are two symbols called end markers.

2)      Reading head: The arrow at the above of finite control is called reading head. As it reads an input symbol it moves one square either at left to right or right to left.

3)       Finite control: It controls the movement of reading head and also over the reading head to the next state.

Finite State Machine (FSM): It is a device which starts working from initial state and after reaching at final state it stops working and it accepts the string. The string is the sequence of the input symbols. In FSM there are 5 tulles which we studied above will be described by directed graphs?

In graph there are vertices in shape of circles called states. The path between two states is called transition. When there is double circle on a state then it will define the final state. When there is an arrow symbol at the starting of any state it means it is a final state. The alphabets are written on paths are called input symbols which together make a string.

In above figure 1,2,3,4 are the states.1 is the initial state.4 is final state and a, b, c alphabets are input symbols. There may be more than one final states and also more than one transition states.The transitions are describes as follows:

1)      1 state reads a symbol “a” and goes to the state 2.

2)      Similarly state 2 reads symbol “b” and go to state 3.

3)       State 3 reads “c” and go to state 4.

4)      State 4 reads “c” and go to state 4.

User interface-GUI and CLI with GNOME and KE

User operating system interface

User interface operating systems are those which support the interaction between user and machine. They are also called HMI means Human –Machine interface. The user interface depends on system to system and also on user to user. User interface not actually a part of the operating system, it generally runs in a separate program. There   are 2 types of user interface:

1)       Command line interpreter

2)       GUI (Graphical User Interface

Graphical User Interface:  The Latest trend is to make the user’s life simpler by providing an attractive, standardized and friendly Graphical User Interface (GUI) which provides images, colors, graphics and icons. It is a mouse based window. It interacts with the user by the help of mouse pointer. The user moves the mouse according to its choice on any image or icon on the screen to represent files, photo gallery, directories etc. Its main advantage is it is responsive for the reduced number of context switches required for the GUI output functions.

First Graphical User Interface appeared on the Xerox Alto computer in 1973.Research taking place early 1970’s at Xerox PARC (Palo Alto Research Center) and developed by ALAN KAY, Douglas Engelbart and a group of other researchers.

Examples of GUI operating system

1)      MAC X OS

2)      Windows XP, Windows 7, Windows Vista

  

Examples of GUI  

1)      GOME (GNU Network Object Model Environment)

2)      KDE (K-desktop Environment)

GNOME

 It is a GUI and a set of computers desktop applications for UNIX based operating systems. Initially CDE was available as a solution, but was never popular on LINUX system due to cost and licensing restrictions. It is an international project that managing file handling, task management with UNIX based operating system. It provides an attractive desktop for users and a platform for building applications. It provide freedom, accessibility, friendliness, organization .This is GNOME 1 version.

K-desktop Environment

It provides an environment for the Guilin is an applicable for UNIX not just LINUX (but was made on LINUX machine).In KDE there is a graphical toolkit and fully featured programming language called QT.QT is made by a commercial company called Trolltech. It also offers a rich set of major technologies like GNOME to improve the GUI or our PC’s desktop. It provides I/O libraries, XML –based GUI class, the component object model, KHTML etc. It has an excellent combination File manager and Web Browser called Konqueror.

Command line interpreter

The user interface is Command line interpreter. It has command based window. It waits for the user command and executes immediately and waits for the next command. Some operating system have command interpreter in their kernel but some use it as a separate program. The command interpreter itself contains a code to execute the command.

Examples:

1)      DCL for VAX

2)      CLI for AOS

3)      SHELL for UNIX

Features provided by command interpreter:

1)      Create a file directory

2)      Delete a file directory

3)      Copy a file directory

4)      Compile a program

5)      Execute  a linked program

6)      Format a disk

7)      List the contents of file directory

8)      Abort a running program

How it works

1)      Firstly user types command in terminal. This command is then transferred from the terminal to the memory buffer

2)      Now find the valid command RUN. It passes the program name to the RUN program

3)      The RUN routine, with the help of system call, locates that file and finds its size.

4)      It will be check out that whether there is space for that size of program or not. If yes, then it will allocate it and if there is no space then it will generate error message.

5)      Now it will transfer the complied program file from disk to available memory locations and it has to right to execute this file. 

                                               

 

Multiprogramming-Execution of two or more programs

Multiprogramming

Multi means many and programming means programs. Therefore Multiprogramming means many programs at a time. Today’s operating system has ability of multiprogramming. Multiprogramming is the interleaved or concurrent execution of two or more programs. The operating system selects a job from job pool and start executing a job, when that job needs to wait for any I/O operations the CPU is switched to another job and control is transfer to another job. Its main advantage is CPU is utilized completely and never remains idle. It was commonly used to keep the CPU busy. Suppose I am typing some in Microsoft Word and also listening music and my anti-virus also scanning my computer, so these all programs are going on simultaneously .Operating system divides time for these programs according to their priorities. When the chance of running of that program comes, it will run up to its given time and after the time is over, next program will run and so on. This process is so much fast that it appears programs are running simultaneously. Windows XP, LINUX are the most recent multiprogramming Operating system.

What controls the computer and acts as intermediately between the user and the computer?

The answer is Operating System. Operating system is nothing, it’s only a program that, when executed it controls the operations of computer. In Zeros generation and First generation of computers there was no operating system in computers. The Third generation computers had Operating system with some major advantages like Multiprogramming, Time-Sharing, Spooling etching Fourth generation there were so many operating systems developed like MS-DOS, UNIX, Windows NT etc.Today's the most recent client version of Windows version is Windows 7 and the most recent server version is Windows 2008 and the most recent mobile version is Windows phone 7.

                                       Operating system is software of programs normally supplied along with the hardware for the effective and easy use of machine. It simply provides the environment within which other programs can do useful work. The two benefits which enhance its utility:

1) Security-Provision of security of information to users.

2) Duplicity-Elimination of duplicate efforts by hundreds of programmers in developing complicated routines.

Block diagram of Operating system:

The operating system controls the hardware and coordinates its use among the various application programs for the various users. The CPU, the Memory and the input/output device provides the basic computing resources for the system. The application programs such as word processor, spreadsheet, compilers and web browsers define the ways in which these resources are used to solve users computing problems.

We next explore operating systems from two viewpoints: that of user and that of system. The CPU, at a moment, can execute only one instruction .If this instruction is from the application program, the machine is said to be in the 'User mode’. If it is executing any operating system instruction, the machine is said to be in the 'System mode'.

User View-The user's view of the computer varies according to the interface being used. The System designed for one user to monopolize its resources is designed mostly for ease of use. Users sit at workstations connected to networks of other workstations and servers. Users share their resources. Therefore the operating system compromise between individual usability and resource utilization.

System View-In this context, we can view an operating system as a resource allocator. The operating system acts as a manger of resources like CPU time, memory space, file storage space, I/O devices. Operating system also view as a control program.A control program manages the execution of user programs to prevent errors and improper use of the computer.

Different Services of Operating System: The type of services that an operating system provides for reading and writing records. The three services are as follows:

1) Information Management

2) Process Management

3) Memory Management

1) Information Management: It refers to a set of services used for storing, retrieving, modifying and removing the information on various devices. Maintaining and enforcing the access controls to ensure that only right people have access information and driving various services, all this is managed by these system services. These services all normally provided by a single user operating system and as well as multiuser operating system.

2) Process Management: In multiuser operating system, a number of users located at different terminals run the same or different programs. At a given time, it can execute only one instructions belonging to any one all of these programs competing for the CPU.The function of operating system in this regard is to keep track of all competing processes, schedule them, dispatch them one after other, but while doing so, try to give each user an impression that he has full control of CPU.

3) Memory Management: These services provided under memory management are directed to keeping track of memory and allocating/deallocating it to various processes. The operating system keeps a list of memory locations.

One set of operating system services provides functions that are helpful to the user.

1) User interface -All operating systems have a user interface. The interface can take several forms. One is batch interface, in which commands and directives to control those commands are entered into files and those files are executed. Another is GUI (Graphical User Interface) is used. The Third one is Trace Command-line interface which uses text command.

2) Program Execution-The system must be able to load and run the program.

3) I/O operations: A running program may require I/O, which may involve file or an I/O device. A user cannot control I/O devices directly. Therefore, the operating system must provide a means to do.

4) File System Manipulation: Operating system provides a variety of file systems. Programs need to read and write files and directories. They also need to create them by name, search for a given file and list file information. These all services are provided by operating system n file systems.

5) Communication: Communications may be implemented by shared memory or message passing, in which packets of information are moved between processes by the operating system.

6) Error detection: Operating system also controls the error occurs in CPU and memory hardware. Debugging facilities can greatly enhance the user’s and programmer's abilities to use the system efficiently.

7) Resource allocation: Different types of resources allocation managed by operating system. Resources may be I/O devices, memory space, CPU cycles etc.

8) Accounting: Operating system also tracks which user use how much and what kinds of computer resources. This record keeping may be used for accounting.

9) Protection and Security: Protection involves ensuring that all access to system resources is controlled. Operating system must protect and secure the information.