Why We Study Automata Theory 6t2z6j

• INTRODUCTION TO AUTOMATA THEORY AND LANGUAGES • NMCA-214

• • • • •

Theory Subject No practical session 100 marks 6 lectures in week Total 60 lectures

Books and Authors Books

Authors

Publisher

Comer

Pearson Education, 4th Ed.

Stallings W

Pearson Education, 2003, 7th Ed

Tanenbaum

Prentice-Hall, 2004, 4th Ed.

Introduction to Automata theory, Languages and Computation Introduction to languages and the theory of computation

Computer Networks

Practical application of Automata Theory Here are some practical, fairly complicated, practical problems that are approached via language theory.

You want to spot duplicate occurrences of a phrase in a document and delete the second occurrence. In essence, you want to substitute a sequence in a language. Does a program contain an assertion violation?

Does a device driver respect certain protocols when interacting with the kernel? The behaviour of a program is a set of executions; in other words, a language. The correctness property is another language. The program correctness problem amounts to a language inclusion check.

Practical application of Automata Theory • Can your software be stuck in an infinite loop? Does a distributed algorithm contain a livelock? We need languages over infinite words, but the language inclusion view still applies. • You want to build a sanitizer to detect malicious Javascript entered into a web application. The set of malicious strings is a language. The set of strings entered into the forms in another language. You want to determine if the intersection of these languages is non-empty. • Run-time monitoring of reactive and mission-critical systems. You want to design a software monitor that oversees the operation of your chemical process or track updates to a financial database. These are at heart language inclusion and intersection problems.

Practical application of Automata Theory • Pattern recognition with its numerous applications. You want to detect patterns in genomic data, in text, in a series of bug reports. These are problems where we are given words from an unknown language and have to guess the language. These are language inference problems. • Given a set of XML documents, you want to reverse engineer a schema that applies to these documents. XML documents can be idealised a trees. A schema is then a specification of a tree language and the schema inference problem is a language inference problem over tree languages. • Many applications require automated arithmetic reasoning. Suppose we fix a logical theory such as Presburger arithmetic, in which we have the natural numbers, addition and the less-than predicate. A formula with n variables represents a set of n-dimensional vectors. A vector is a sequence of digits and can be encoded as a word. A predicate is then a set of words; a language. Logical operations such as conjunction, disjunction and negation become intersection, union and complement of languages (existential quantification is a kind of projection).

• There are several reasons to study of automata and complexity is an important part of the core of computer science. • 1. Introduction to Finite Automata • 2. Structural Representation • 3. Automata and Complexity

Introduction to Finite Automata Finite Automata are a useful model for many important kinds of hardware and software • •

Software for deg and checking the behavior of digital circuits The Le i al a al zer of a t pi al o piler , that is , the o piler component that breaks the • input text into logical units, such as identifiers, keywords, and punctuation. • Software for scanning large bodies of text, such as collections of Web pages, to find

occurrences of words, phrases, or other patterns. • Software for ing systems of all types that have a finite number of distinct states, such as • communications protocols or protocols for secure exchange of information.

Structural Representations:

• There are two important notations there are not automation-like, but play an important role in the study of automata and their applications • 1. Grammars are useful models when software that processes data with a recursive structure. • 2. Regular Expressions are denoted the structure of data, especially text strings.

Automata and Complexity

• Automata are essential for the study of the limits of computation. • There are two important issues. • . What a a o puter do at all? This stud is alled decidability , a d the problems that can • e sol ed o puter are alled decidable. . • . What a a o puter do effi ie tl ? This stud is alled i tra ta ilit , and the problems that • can be solved by a computer using no more time than some slowly growing function of the • size of the i put are alled tractable. Ofte , e all pol o ial fu tio s to e slo l • gro i g , hile fu tio s that gro s faster tha a pol o ial are deemed to grow too fast.

Automata theory and formal languages are the base of • current compilers, • regular expressions, • parsers, • web-scrappers, • natural language processing (NLP), • state machines based on markov chains

Syllabus • • • • •

UNIT 1:Basic concepts of Automata Theory 11L UNIT 2: Regular Expressions and Languages 10L UNIT 3: Non-Regular Grammars 24L UNIT 4: Turing Machines 8 L UNIT 5: Undecidability 7L

Unit 1:Basic concepts of Automata Theory • • • • • • •

Alphabets, Strings and Languages, Deterministic FiniteAutomata (DFA) Nondeterministic Finite Automata (NFA), Language of DFA and NFA. NFA ith ε-transitions, Language ofNFA with ε-transitions Equivalence of NFA and DFA.

UNIT 2: Regular Expression • Regular Expressions and Languages: Introduction, Definition of regular expression, • Klee ’sTheore , • Equivalence of regular expression and Finite Automata, • Pumping Lemma for regular • Languages, Closure properties of Regular Languages, • Decision properties of Regular Languages, • Finite Automata with Output: Moore and Mealy Machine, • Equivalence of Moore and Mealy Machines.

Unit 3: Non-Regular Grammars • Non-Regular Grammars: Definition of Grammar, Classification of Grammars, • Chomosky's Hierarchy. • Context Free Grammars (CFG) and Context Free Languages (CFL) • Derivation trees, • Ambiguous Grammars, • Simplification of Grammars, • Normal forms of CFGs: CNF and GNF, • Closure properties of CFLs, • Decision Properties of CFLs, • Pumping lemma for CFLs. Push Down • Automata (PDA): Definition and Description, • Language of PDA and its applications.

Unit 4:Turing Machines • • • •

Turing Machines: Introduction, Basic Features of a Turing Machine, Language of a Turing Machine, Variants of Turing Machine: – Multitapes, – Nondeterministic Turing Machine, – Universal Turing Machine.

• Turing Machine as Computer of Integer functions, • Halting problem of Turing Machine, • Church-TuringThesis.

Unit 5:Undecidability • • • • • •

Undecidability: Introduction Undecidable problems about Turing Machines, Rice's Theorem, Post'sCorrespondence problem (P) Modified P Tractable and Intractable Problems: P and NP, NPComplete Problems,

• Introduction to recursive function theory.

Advantage of Data Communication and Computer Network • • • • • • • • • • •

Communication Data sharing Instant and multiple accesses Video conferencing Internet Service Broad casting Photographs and large files Saves Cost Remote access and Reliable Data transmission

Syllabus • Unit I (17 Sessions) Fundamentals of Communication System : 17 L • Unit II (08 Sessions) LAN topologies: 8 L • Unit III (07 Sessions) Networks and accessories:7 L • Unit IV (10 Sessions) OSI Model: 10 L • Unit V (13 Sessions) Mobile Communication: 13 L Lectures = L

• Unit I (08 Sessions) Fundamentals of Communication System Communication Links,  Communication System Formats  Character Codes, Digital Data Rates; Asynchronous and Synchronous Data Types of signals: AM; FM; PM; PCM; PDM;TDMA; FDMA; SDMA; CDMA; ASK; FSK; Error detection and correction codes; Hamming codes.

Unit II (08 Sessions) LAN topologies Workstation; Server; Cables; Types of Ethernet; Broadband and base-band; Optical Fibers; Network Interface Card.

Unit III (08 Sessions) Networks and accessories: • • • • •

LAN, MAN, WAN; Hub; Bridges; Switches; Routers; Gateways Cell Relay; Frame Relay; ISDN; B-ISDN

• Unit IV (08 Sessions) OSI Model; Broadcasting;  Multicasting  Point-to-point communication;  IP Addressing, Concepts of Port; Socket;  ATM; Tunneling;  Virtual Private Network Network Operating systems: Unix; Linux; Windows.

Unit V (08 Sessions) Mobile Communication: • Applications of Mobile Communication; Wireless Communication: • Bandwidth, • Transmission Impairment, • Interference, • Terrestrial Microwave, Broadcast Radio, Infrared & Light Waves, • Mobile Internet & WML: Mobile IP, • Wireless T& UDP, WAP, WML

History of Data Communication • Transistor developed by Bell Labs (which is now ???) 1947 • Hush-a-Phone Case • Carterphone case • MCI and Long Distance • Creatio of et orks LAN’s a d WAN’s • Data Link Protocols • Microcomputers