FORMAL LANGUAGES & AUTOMATA THEORY (FLAT) Syllabus of Andhra University 2017 to 19

-
MSCS 2.1   FORMAL LANGUAGES & AUTOMATA THEORY
 Instruction: 3 Periods + 1 Tut/week                                                                                  Credits:4
Internal: 30 Marks                    University Exam: 70 Marks                             Total: 100 Marks 

1.     Finite Automata and Regular Expressions: Basic Concepts  of Finite State Systems, Deterministic and Non-Deterministic Finite Automata, Finite Automata with 
      є-moves, Regular Expressions, Mealy and Moore Machines, Two-Way Finite Automate, Applications of FSM. 

2.    Regular sets & Regular Grammars: Basic Definitions of Formal Languages and Grammars, Regular Sets and Regular Grammars, Closure Properties of Regular Sets, Pumping Lemma for Regular Sets, Decision Algorithm for Regular Sets, MyhillNerode Theorem, Minimization of Finite Automata. 


3.    Context Free Grammars and Languages: Context Free Grammars and Languages, Derivation Trees, Simplification  of Context Free Grammars, Normal Forms, Pumping Lemma for CFL, Closure properties of CFL’s, Decision Algorithm for CFL. 

4.    Push down Automata:  Informal Description, Definitions, Push-Down Automata and Context free         Languages, Parsing and Push-Down Automata. 

5.    Turing Machines: The Definition of Turing Machine, Design and Techniques for Construction of Turing Machines, Combining Turing Machines.  

6.    Universal Turing Machines and Undecidability : Universal Turing Machines. The Halting Problem, Variants of Turing Machines, Restricted Turing Machines, 
      Decidable & Undecidable  Problems - Post Correspondence Problem.

7.      Chomsky Hierarchy of Languages: Regular Grammars, Unrestricted Grammars, Context Sensitive languages, Relationship between Classes of Languages.  

Text books: 

1. Introduction to Automata Theory, Languages and Computations – J.E.Hopcroft, & J.D.          Ullman,Pearson Education Asia. 

Reference books: 


1. Introduction to languages and theory of computation – John C. Martin (MGH) 

2. Theory of Computation, KLP Mishra and N. Chandra Sekhar, IV th Edition, PHI 

3. Introduction to Theory of Computation – Michael Sipser (Thomson Nrools/Cole)   

Comments

Post a Comment

Popular posts from this blog

What is OSI model ? Explain the Layers of OSI model with diagram .

-
Image
What is OSI model ? Explain the Layers of OSI model with diagram . What is OSI model? The OSI model (Open System Interconnection) model defines a computer networking framework to implement protocols in seven layers. A protocol in the networking terms is a kind of negotiation and rule in between two networking entities. Layers of OSI model: Physical layer The Physical layer is also called as the Layer 1. Here are the basic functionalities of the Physical layer: ·        Responsible for electrical signals, light signal, radio signals etc. ·        Hardware layer of the OSI layer ·        Devices like repeater, hub, cables, ethernet work on this layer ·        Protocols like RS232, ATM, FDDI, Ethernet work on this layer Data Link layer The data link layer is also called as the Layer 2 of the OSI model. Here are the basic functionalities of the data link layer: ·        Responsible for encoding and decoding of the electrical signals into bits. ·
Read more

BUS AND MEMORY TRANSFERS

-
Image
BUS AND MEMORY TRANSFERS          A typical digital computer has many registers, and paths must be provided to transfer in formation form one register to another. The number of wires will be excessive if separate lines are used between each register and all other registers in the system. A more efficient scheme for transferring information between registers in a multiple-register configuration is a common bus system. A bus structure consists of a set of common lines, one for each bit of a register, through which binary information is transferred one at a time. Control signals determine which register is selected by the onus during each particular register transfer.           One way of constructing a common bus system is with multiplexers. The multiplexers select the source register whose binary information is then placed on the bus. The construction of a bus system for four registers is shown is Fig . Each register has four bits, numbered 0 through 3. The bus consists
Read more