Automata Theory 4th Sem - VSSUT
AUTOMATA THEORYDigital Notes ByBIGHNARAJ NAIKAssistant ProfessorDepartment of Master in Computer ApplicationVSSUT, Burla
Syllabus4th SEMESTER MCAF.M : 70MCA 207AUTOMATA THEORY (3-1-0)Cr.-4Module – IIntroduction to Automata: The Methods Introduction to Finite Automata, StructuralRepresentations, Automata and Complexity.Proving Equivalences about Sets, The Contrapositive, Proof by Contradiction,Inductive Proofs: General Concepts of Automata Theory: Alphabets Strings, Languages,Applications of Automata Theory.Module – IIFinite Automata: The Ground Rules, The Protocol, Deterministic Finite Automata: Definitionof a Deterministic Finite Automata, How a DFA Processes Strings, Simpler Notations forDFA’s, Extending the Transition Function to Strings, The Language of a DFANondeterministic Finite Automata: An Informal View. The Extended Transition Function, TheLanguages of an NFA, Equivalence of Deterministic and Nondeterministic Finite Automata.Finite Automata With Epsilon-Transitions: Uses of -Transitions, The Formal Notation for an -NFA, Epsilon-Closures, Extended Transitions and Languages for -NFA’s, Eliminating Transitions.Module – IIIRegular Expressions and Languages: Regular Expressions: The Operators of regularExpressions, Building Regular Expressions, Precedence of Regular-Expression Operators,Precedence of Regular-Expression OperatorsFinite Automata and Regular Expressions: From DFA’s to Regular Expressions, ConvertingDFA’s to Regular Expressions, Converting DFA’s to Regular Expressions by Eliminating States,Converting Regular Expressions to Automata.Algebraic Laws for Regular Expressions:Properties of Regular Languages: The Pumping Lemma for Regular Languages, Applications ofthe Pumping Lemma Closure Properties of Regular Languages, Decision Properties of RegularLanguages, Equivalence and Minimization of Automata,Module – IVContext-Free Grammars and Languages: Definition of Context-Free Grammars, DerivationsUsing a Grammars Leftmost and Rightmost Derivations, The Languages of a Grammar,Parse Trees: Constructing Parse Trees, The Yield of a Parse Tree, Inference Derivations, andParse Trees, From Inferences to Trees, From Trees to Derivations, From Derivation to RecursiveInferences,
Applications of Context-Free Grammars: Parsers, Ambiguity in Grammars and Languages:Ambiguous Grammars, Removing Ambiguity From Grammars, Leftmost Derivations as a Wayto Express Ambiguity, Inherent AnbiguityModule – VPushdown Automata: Definition Formal Definition of Pushdown Automata, A GraphicalNotation for PDA’s, Instantaneous Descriptions of a PDA,The Languages of a PDA: Acceptance by Final State, Acceptance by Empty Stack, From EmptyStack to Final State, From Final State to Empty StackEquivalence of PDA’s and CFG’s: From Grammars to Pushdown Automata, From PDA’s toGrammarsDeterministic Pushdown Automata: Definition of a Deterministic PDA, Regular Languages andDeterministic PDA’s, DPDA’s and Context-Free Languages, DPDA’s and AmbiguousGrammarsModule – VIProperties of Context-Free Languages: Normal Forms for Context-Free Grammars, ThePumping Lemma for Context-Free Languages, Closure Properties of Context-Free Languages,Decision Properties of CFL’sModule - VIIIntroduction to Turing Machines: The Turing Machine: The Instantaneous Descriptions forTuring Machines, Transition Diagrams for Turing Machines, The Language of a TuringMachine, Turing Machines and HaltingProgramming Techniques for Turing Machines, Extensions to the Basic Turing Machine,Restricted Turing Machines, Turing Machines and Computers,Module - VIIIUndecidability: A Language That is Not Recursively Enumerable, Enumerating the BinaryStrings, Codes for Turing Machines, The Diagonalization LanguageAn Undecidable Problem That Is RE: Recursive Languages, Complements of Recursive and RElanguages, The Universal Languages, Undecidability of the Universal LanguageUndecidable Problems About Turing Machines: Reductions, Turing Machines That Accept theEmpty LanguagePost’s Correspondence Problem: Definition of Post’s Correspondence Problem, The “Modified”PCPOther Undecidable Problems: Undecidability of Ambiguity for CFG’s
REFERENCE BOOKS1. Hopcroft, Ullman “ Theory of Computation & Formal Languages”, TMH.2. FORMAL LANGUAGES AND AUTOMATA THEORY, H S Behera, JanmenjoyNayak , Hadibandhu Pattnayak, Vikash Publishing, New Delhi.3. Anand Sharma, “Theory of Automata and Formal Languages”, Laxmi Publisher.
Formal languageThe alphabet of a formal language is the set of symbols, letters, or tokens from which the stringsof the language may be formed; frequently it is required to be finite. The strings formed from thisalphabet are called words, and the words that belong to a particular formal language aresometimes called well-formed words or well-formed formulas. A formal language is oftendefined by means of a formal grammar such as a regular grammar or context-free grammar, alsocalled its formation rule.The field of formal language theory studies the purely syntactical aspects of such languages—that is, their internal structural patterns. Formal language theory sprang out of linguistics, as away of understanding the syntactic regularities of natural languages. In computer science, formallanguages are often used as the basis for defining programming languages and other systems inwhich the words of the language are associated with particular meanings or semantics.A formal languageL over an alphabet Σ is a subset of Σ*, that is, a set of words over thatalphabet.In computer science and mathematics, which do not usually deal with natural languages, theadjective "formal" is often omitted as redundant.While formal language theory usually concerns itself with formal languages that are described bysome syntactical rules, the actual definition of the concept "formal language" is only as above: a(possibly infinite) set of finite-length strings, no more nor less. In practice, there are manylanguages that can be described by rules, such as regular languages or context-free languages.The notion of a formal grammar may be closer to the intuitive concept of a "language," onedescribed by syntactic rules.Formal languageA formal grammar (sometimes simply called a grammar) is a set of formation rules for strings ina formal language. The rules describe how to form strings from the language's alphabet that are
valid according to the language's syntax. A grammar does not describe the meaning of the stringsor what can be done with them in whatever context—only their form.A formal grammar is a set of rules for rewriting strings, along with a "start symbol" from whichrewriting must start. Therefore, a grammar is usually thought of as a language generator.However, it can also sometimes be used as the basis for a "recognizer"—a function in computingthat determines whether a given string belongs to the language or is grammatically incorrect. Todescribe such recognizers, formal language theory uses separate formalisms, known as automatatheory. One of the interesting results of automata theory is that it is not possible to design arecognizer for certain formal languages.AlphabetAn alphabet, in the context of formal languages, can be any set, although it often makes sense touse an alphabet in the usual sense of the word, or more generally a character set such as ASCII.Alphabets can also be infinite; e.g. first-order logic is often expressed using an alphabet which,besides symbols such as , , and parentheses, contains infinitely many elements x0, x1, x2, that play the role of variables. The elements of an alphabet are called its letters.wordA word over an alphabet can be any finite sequence, or string, of letters. The set of all wordsover an alphabet Σ is usually denoted by Σ* (using the Kleene star). For any alphabet there isonly one word of length 0, the empty word, which is often denoted by e, ε or λ. By concatenationone can combine two words to form a new word, whose length is the sum of the lengths of theoriginal words. The result of concatenating a word with the empty word is the original word.Operations on languagesCertain operations on languages are common. This includes the standard set operations, such asunion, intersection, and complement. Another class of operation is the element-wise applicationof string operations.
Examples: suppose L1 and L2 are languages over some common alphabet. The concatenation L1L2 consists of all strings of the form vw where v is a string from L1and w is a string from L2. The intersection L1 L2 of L1 and L2 consists of all strings which are contained in bothlanguages The complement L of a language with respect to a given alphabet consists of all stringsover the alphabet that are not in the language. The Kleene star: the language consisting of all words that are concatenations of 0 or morewords in the original language; Reversal:oLet e be the empty word, then eR e, andofor each non-empty word w x1 xn over some alphabet, let wR xn x1,othen for a formal language L, LR {wR w L}.String homomorphismSuch string operations are used to investigate closure properties of classes of languages. A classof languages is closed under a particular operation when the operation, applied to languages inthe class, always produces a language in the same class again. For instance, the context-freelanguages are known to be closed under union, concatenation, and intersection with regularlanguages, but not closed under intersection or complement. The theory of trios and abstractfamilies of languages studies the most common closure properties of language families in theirown right.Language“A language is a collection of sentences of finite length all constructed from a finite alphabet ofsymbols.In general, if is an alphabet and L is a subset of *, then L is said to be a languageover, or simply a language if is understood. Each element of L is said to be a sentenceor a word or astringof the language.
Example 1 {0, 11, 001}, { , 10}, and {0, 1}* are subsets of {0, 1}*, and so they are languagesover the alphabet {0, 1}.The empty set Ø and the set { } are languages over every alphabet. Ø is a language that containsno string. { } is a language that contains just the empty string.The unionof two languages L1 and L2, denoted L1 L2, refers to the language that consists of allthe strings that are either in L1 or in L2, that is, to { x x is in L1 or x is in L2 }. The intersectionofL1 and L2, denoted L1 L2, refers to the language that consists of all the strings that are both in L1and L2, that is, to { x x is in L1 and in L2 }. The complementationof a language L over , or justthe complementation of L when is understood, denoted, refers to the language that consists ofall the strings over that are not in L, that is, to { x x is in * but not in L }.Example 2 Consider the languages L1 { , 0, 1} and L2 { , 01, 11}. The union of theselanguages is L1 L2 { , 0, 1, 01, 11}, their intersection is L1 L2 { }, and the complementationof L1 is {00, 01, 10, 11, 000, 001, . . . }.Ø L L for each language L. Similarly, Ø L Ø for each language L. On the other hand, * and Ø for each alphabet .The differenceof L1 and L2, denoted L1 - L2, refers to the language that consists of all the stringsthat are in L1 but not in L2, that is, to { x x is in L1 but not in L2 }. The crossproduct of L1 andL2, denoted L1 L2, refers to the set of all the pairs (x, y) of strings such that x is in L1 and y is inL2, that is, to the relation { (x, y) x is in L1 and y is in L2 }. The compositionof L1 with L2,denoted L1L2, refers to the language { xy x is in L1 and y is in L2 }.Example 3 If L1 { , 1, 01, 11} and L2 {1, 01, 101} then L1 - L2 { , 11} and L2 - L1 {101}.On the other hand, if L1 { , 0, 1} and L2 {01, 11}, then the cross product of these languagesis L1 L2 {( , 01), ( , 11), (0, 01), (0, 11), (1, 01), (1, 11)}, and their composition is L1L2 {01,11, 001, 011, 101, 111}.L - Ø L, Ø - L Ø, ØL Ø, and { }L L for each language L.
Li will also be used to denote the composing of i copies of a language L, where L0 is defined as {}. The set L0 L1 L2 L3 . . . , called the Kleeneclosure or just the closure of L, will be denotedby L*. The set L1 L2 L3 , called the positiveclosure of L, will be denoted by L .Li consists of those strings that can be obtained by concatenating i strings from L. L* consists ofthose strings that can be obtained by concatenating an arbitrary number of strings from L.Example 4 Consider the pair of languages L1 { , 0, 1} and L2 {01, 11}. For theselanguages L1 2 { , 0, 1, 00, 01, 10, 11}, and L2 3 {010101, 010111, 011101, 011111, 110101,110111, 111101, 111111}. In addition, is in L1*, in L1 , and in L2* but not in L2 .The operations above apply in a similar way to relations in * *, when and are alphabets.Specifically, the unionof the relations R1 and R2, denoted R1 R2, is the relation { (x, y) (x, y) isin R1 or in R2 }. The intersectionof R1 and R2, denoted R1 R2, is the relation { (x, y) (x, y) is inR1 and in R2 }. The compositionof R1 with R2, denoted R1R2, is the relation { (x1x2, y1y2) (x1,y1) is in R1 and (x2, y2) is in R2 }.GrammarIt is often convenient to specify languages in terms of grammars. The advantage in doing soarises mainly from the usage of a small number of rules for describing a language with a largenumber of sentences. For instance, the possibility that an English sentence consists of a subjectphrase followed by a predicate phrase can be expressed by a grammatical rule of the form sentence subject predicate . (The names in angular brackets are assumed to belong to thegrammar metalanguage.) Similarly, the possibility that the subject phrase consists of a nounphrase can be expressed by a grammatical rule of the form subject noun .G is defined as a mathematical system consisting of a quadruple N, , P, S , whereN : is an alphabet, whose elements are called nonterminalsymbols.: is an alphabet disjoint from N, whose elements are called terminalsymbols.P :is a relation of finite cardinality on (N)*, whose elements are called productionrules.Moreover, each production rule ( , ) in P, denoted, must have at least one nonterminal
symbol in . In each such production rule, is said to be the left-handsidehandside of the production rule,and is said to be the right-handsihandside of the production rule.S is a symbol in N called the start, or sentence, symbol.Types of grammarsPrescriptive: prescribes authoritative norms for a languageDescriptive: attempts to describe actual usage rather thanenforce arbitrary rulesFormal: a precisely defined grammar, such as context-freecontextGenerative: a formal grammar that can generate naturallanguage expressionsChomsky hierarchy of languages.The Chomsky hierarchy consists of the following levels:Type-0 grammars (unrestrictedunrestricted grammars)grammars include all formal grammars. They generate exactlyall languages that can be recognized by a Turing machine. These languages are also known asthe recursively enumerableumerable languages.languages Note that this is different from the recursive languageswhich can be decided by an always-haltingalwaysTuring machine.Type-1 grammars (context-sensitivesensitive grammars)grammars generate the context-sensitivesensitive languages.languages Thesegrammars have rules of the formwithterminals and nonterminals. The stringsanda nonterminal andmay be empty, but,andstrings ofmust be nonempty.noThe ruleis allowed if does not appear on the right side of any rule. The languages described bythese grammars are exactly all languages that can be recognized by a linear bounded automaton(a nondeterministic Turing machine whose tape is bounded by a constant times the length of theinput.)Type-2 grammars (context-freefree grammars)grammars generate the context-freefree languages.languages These aredefined by rules of the formwitha nonterminal and a string of terminals andnonterminals. Theseese languages are exactly all languages that can be recognized by a nonnon
deterministic pushdown automaton.automaton Context-freefree languages are the theoretical basis for thesyntax of most programming languageslanguages.Type-3 grammars (regularregular grammars)generategrammarsthe regular languages. Such a grammar restrictsits rules to a single nonterminal on the left-handleftside and a right-hand side consisting of a singleterminal, possibly followed (or preceded, but not both in the same grammar) by a singlenonterminal. The ruleis also allowed here ifdoes not appear on the right side of anyrule. These languages are exactly all languages ththat can be decided by a finite state automaton.automatonAdditionally, this family of formal languages can be obtained by regular expressions.expressions Regularlanguages are commonly used to define search patterns and the lexical structure of programminglanguages.Examples:1. The language consists of all strings begin with 0.{0}{0, 1}*2. The language consists of alll strings begin with 0, and end with 1.{0}{0, 1}*{1}3. The language consists of all strings with odd lengths.{0, 1}2n 1, n 1, 2, . . .
4. The language consists of all strings with substring of three consecutive 0.{0, 1}*000{0, 1}*5. The language consists of all strings without substring of three consecutive 0.{001, 01, 1}*Regular grammarA regular grammar is any right-linear or left-linear grammar.A right regular grammar (also called right linear grammar) is a formal grammar (N, Σ, P, S) suchthat all the production rules in P are of one of the following forms:B a - where B is a non-terminal in N and a is a terminal in ΣB aC - where B and C are in N and a is in ΣB ε - where B is in N and ε denotes the empty string, i.e. the string of length 0.In a left regular grammar (also called left linear grammar), all rules obey the formsA a - where A is a non-terminal in N and a is a terminal in ΣA Ba - where A and B are in N and a is in ΣA ε - where A is in N and ε is the empty string.An example of a right regular grammar G with N {S, A}, Σ {a, b, c}, P consists of thefollowing rulesS aSS bAA εA cAandS is the start symbol. This grammar describes the same language as the regular expressiona*bc*.Extended regular grammarsAn extended right regular grammar is one in which all rules obey one of1. B a - where B is a non-terminal in N and a is a terminal in Σ2. A wB - where A and B are in N and w is in Σ*3. A ε - where A is in N and ε is the empty string.Some authors call this type of grammar a right regular grammar (or right linear grammar) and thetype above a strictly right regular grammar (or strictly right linear grammar).
An extended left regular grammar is one in which all rules obey one of1. A a - where A is a non-terminal in N and a is a terminal in Σ2. A Bw - where A and B are in N and w is in Σ*3. A ε - where A is in N and ε is the empty string.Regular expressionA regular expression (or regexp, or pattern, or RE) is a text string that describes some(mathematical) set of strings. A RE r matches a string s if s is in the set of strings described by r.Regular Expressions have their own notation. Characters are single letters for example ‘a’, ‘’(single blank space), ‘1’ and ‘-’ (hyphen). Operators are entries in a RE that match one or morecharacters.Regular expressions consist of constants and operator symbols that denote sets of strings andoperations over these sets, respectively. The following definition is standard, and found as suchin most textbooks on formal language theory. Given a finite alphabet Σ, the following constantsare defined as regular expressions: (empty set) denoting the set . (empty string) ε denoting the set containing only the "empty" string, which has nocharacters at all. (literal character) a in Σ denoting the set containing only the character a.Given regular expressions R and S, the following operations over them are defined to produceregular expressions: (concatenation) RS denoting the set { αβ
FORMAL LANGUAGES AND AUTOMATA THEORY, H S Behera , Janmenjoy Nayak , Hadibandhu Pattnayak , Vikash Publishing, New Delhi. 3. Anand Sharma, “Theory of Automata and Formal Languages”, Laxmi Publisher. Formal language The alphabet of a formal language is the set of s
Advanced Automata Theory is a lecture which will rst review the basics of formal languages and automata theory and then give insight into speci c topics from wider area of automata theory. In computer science, automata are an important tool for many theoretical results and various types of automata
3rd Sem. 4 4 4 - 4 - 16 4th Sem. 4 4 4 - 4 - 16 5th-Sem. - - - 4 12 16 6th Sem. - - - - 4 12 16 Total credit 16 16 16 8 16 24 96 The format of Skill Enhancement Courses is given below: Skill Enhancement Courses from 3rd thto 6 semester S. No. sem Combination of three courses Semester and Course Code 3rd 4th sem 5th 6th sem
Sem 1 5 3 9 17 Sem 2 4 3 9 16 Sem 3 4 3 9 2 18 Sem 4 4 3 9 16 Sem 5 4 3 9 2 18 Sem 6 3 3 10 2 18 Sem 7 16 16 Sem 8 12 12 Total Credit Hours 24 18 83 6 131 Credit Hours Percentage 18.32% 13.74% 63.35% 4.6% 100% Total credit hours suggested is 131 with the highest weightage goes to the programmes core subjects which takes 63 % or 83 credit.
6. MCA: 1st,3rd & 5th Semester (Regular/Re-Appear) & 6th Sem (Only Re Appear) 2 Yr MBA(General)/MBA(Power Mgt/BE/Executive) 1st, 3rd Sem. (Regular/Re-Appear) & 4th Sem. (Only Re-Appear) 5 Year MBA Integrated : 1st, 3rd, 5th, 7th, 9th Sem. (Regular/Re- Appear) & Sem10th ( only Re-Appear) MHMCT/MHM/ MTTM/MTM : 1st ,3rd Sem (Regular/Re-Appear) & 4th Sem (Only Re-Appear)
Automata and Formal Languages II Tree Automata Peter Lammich SS 2015 1/161. Overview by Lecture Apr 14: Slide 3 Apr 21: Slide 2 Apr 28: Slide 4 May 5: Slide 50 . Finite tree automata: Basic theory (TATA Ch. 1) Pumping Lemma, Clo
Complexity, the Central Concepts of Automata Theory - Alphabets, Strings, Languages, Problems. Deterministic Finite Automata, Nondeterministic Finite Automata, an application: Text Search, Finite Automata with Epsilon-Transitions, Finite automata with output - Mealy and Moore machines, Equivalence of Mealy and Moore machines.
properties of bipolar general fuzzy switchboard automata are discussed in term of switching and commutative by proving the theorems that are related into these concepts. . 2.3 Automata theory 18 2.4 Optimisation problems 23 2.4.1 Critical path problem 23 . Deterministic finite automata FSM - Finite state machine FSA - Finite state automata .
the transactions are difficult to discern. This makes it difficult to determine the overall size of activity and to know what the fair price is for a particular technology. And, of course, in highly inefficient markets a good deal of potentially valuable trade in innovation does not occur. The costs are so high and the potential value so difficult to perceive that innovation often sits “on .
