[PDF] Formal Languages and Automata Theory

View - Download Formal Languages and Automata Theory

Previous PDF

Next PDF

Formal Languages and Automata Theory

D. Goswami and K. V. Krishna

November 5, 2010

Contents

1 Mathematical Preliminaries 3

2 Formal Languages 4

2.1 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 Finite Representation . . . . . . . . . . . . . . . . . . . . . . . 13

2.4.1 Regular Expressions . . . . . . . . . . . . . . . . . . . 13

3 Grammars 18

3.1 Context-Free Grammars . . . . . . . . . . . . . . . . . . . . . 19

3.2 Derivation Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.2.1 Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.3 Regular Grammars . . . . . . . . . . . . . . . . . . . . . . . . 32

3.4 Digraph Representation . . . . . . . . . . . . . . . . . . . . . 36

4 Finite Automata 38

4.1 Deterministic Finite Automata . . . . . . . . . . . . . . . . . 39

4.2 Nondeterministic Finite Automata . . . . . . . . . . . . . . . 49

4.3 Equivalence of NFA and DFA . . . . . . . . . . . . . . . . . . 54

4.3.1 Heuristics to Convert NFA to DFA . . . . . . . . . . . 58

4.4 Minimization of DFA . . . . . . . . . . . . . . . . . . . . . . . 61

4.4.1 Myhill-Nerode Theorem . . . . . . . . . . . . . . . . . 61

4.4.2 Algorithmic Procedure for Minimization . . . . . . . . 65

4.5 Regular Languages . . . . . . . . . . . . . . . . . . . . . . . . 72

4.5.1 Equivalence of Finite Automata and Regular Languages 72

4.5.2 Equivalence of Finite Automata and Regular Grammars 84

4.6 Variants of Finite Automata . . . . . . . . . . . . . . . . . . . 89

4.6.1 Two-way Finite Automaton . . . . . . . . . . . . . . . 89

4.6.2 Mealy Machines . . . . . . . . . . . . . . . . . . . . . . 91

1

5 Properties of Regular Languages 94

5.1 Closure Properties . . . . . . . . . . . . . . . . . . . . . . . . 94

5.1.1 Set Theoretic Properties . . . . . . . . . . . . . . . . . 94

5.1.2 Other Properties . . . . . . . . . . . . . . . . . . . . . 97

5.2 Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . 104

2

Chapter 1

Mathematical Preliminaries

3

Chapter 2

Formal Languages

A language can be seen as a system suitable for expression of certain ideas, facts and concepts. For formalizing the notion of a language one must cover all the varieties of languages such as natural (human) languages and program- ming languages. Let us look at some common features across the languages. One may broadly see that a language is a collection of sentences; a sentence is a sequence of words; and a word is a combination of syllables. If one con- siders a language that has a script, then it can be observed that a word is a sequence of symbols of its underlying alphabet. It is observed that a formal learning of a language has the following three steps. 1. Learning its alphabet - the symbols that are used in the language. 2. Its words - as various sequences of symbols of its alphabet. 3. Formation of sentences - sequence of various words that follow certain rules of the language. In this learning, step 3 is the most di±cult part. Let us postpone to discuss construction of sentences and concentrate on steps 1 and 2. For the time being instead of completely ignoring about sentences one may look at the common features of a word and a sentence to agree upon both are just se- quence of some symbols of the underlying alphabet. For example, the English sentence "The English articles - a, an and the - are categorized into two types: indefinite and definite." may be treated as a sequence of symbols from the Roman alphabet along with enough punctuation marks such as comma, full-stop, colon and further one more special symbol, namelyblank-spacewhich is used to separate two words. Thus, abstractly, a sentence or a word may be interchangeably used 4 for a sequence of symbols from an alphabet. With this discussion we start with the basic de¯nitions of alphabets and strings and then we introduce the notion of language formally. Further, in this chapter, we introduce some of the operations on languages and discuss algebraic properties of languages with respect to those operations. We end the chapter with an introduction to ¯nite representation of languages via regular expressions.

2.1 Strings

We formally de¯ne analphabetas a non-empty ¯nite set. We normally use the symbolsa;b;c;:::with or without subscripts or 0;1;2;:::, etc. for the elements of an alphabet. Astringover an alphabet § is a ¯nite sequence of symbols of §. Although one writes a sequence as (a1;a2;:::;an), in the present context, we prefer to write it asa1a2¢¢¢an, i.e. by juxtaposing the symbols in that order. Thus, a string is also known as awordor asentence. Normally, we use lower case letters towards the end of English alphabet, namelyz;y;x;w;etc., to denote strings.

Example 2.1.1.

quotesdbs_dbs2.pdfusesText_3

[PDF] formal languages and automata theory mcq

[PDF] formal languages and automata theory notes

[PDF] formal languages and automata theory nptel

[PDF] formal languages and automata theory ppt

[PDF] formal languages and automata theory problems and solutions

[PDF] formal languages and automata theory syllabus

[PDF] formal languages and automata theory tutorial

[PDF] formal languages and their relation to automata pdf

[PDF] formal report sample for students

[PDF] formal report writing example

[PDF] formal report writing examples igcse

[PDF] formal report writing format for students

[PDF] formal report writing sample for students

[PDF] formal versus informal language pdf

[PDF] formal vs informal language pdf