[PDF] Automata Theory and Languages Automata theory : the study of

View - Download Automata Theory and Languages

Previous PDF

Next PDF

Automata Theory andLanguages

SITE : http://www.info.univ-tours.fr/˜mirian/

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 1/19

Introduction to Automata Theory

Automata theory :the study of abstract computing devices, or "machines"Before computers (1930),A. Turingstudied an abstract machine (Turing

machine) that had all the capabilities of today' s computers (concerning what they could compute). His goal was to describe precisely the boundary between whata computing machine could do and what it could not do. Simpler kinds of machines (finite automata) were studied by a number of

researchers anduseful for a variety of purposes.Theoretical developments bear directly on what computer scientists do today

Finite automata, formal grammars: design/ construction ofsoftwareTuring machines: help us understand what we can expect from asoftwareTheory of intractable problems: are we likely to be able to write a program

to solve a given problem? Or we should try an approximation, aheuristic... Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 2/19

Why Study Automata Theory?

Finite automata are a useful model for many important kinds of software and hardware:

1. Software for designing and checking the behaviour of digital circuits

2. The lexical analyser of a typical compiler, that is, the compiler component that

breaks the input text into logical units

3. Software for scanning large bodies of text, such as collections of Web pages, to

find occurrences of words, phrases or other patterns

4. Software for verifying systems of all types that have a finite number of distinct

states, such as communications protocols of protocols for secure exchange information Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 3/19

The Central Concepts of Automata Theory

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 4/19

Alphabet

A finite, nonempty set of symbols.Symbol:ΣExamples:

The binary alphabet:Σ ={0,1}The set of all lower-case letters:Σ ={a,b,...,z}The set of all ASCII characters

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 5/19

Strings

Astring(or sometimes aword) is a finite sequence of symbols chosen from some alphabetExample :01101and111are strings from the binary alphabetΣ ={0,1} Empty string: the string with zero occurrences of symbols This string is denoted by?and may be chosen from any alphabet whatsoever.Length of a string: the number of positions for symbols in the stringExample :01101has length5 •There are only two symbols (0and1) in the string01101, but5positions for symbols

Notation of length ofw:|w|Example

:|011|= 3and|?|= 0 Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 6/19

Powers of an alphabet (1)

IfΣis an alphabet, we can express the set of all strings of a certain length from that alphabet by using the exponential notation: Σk: the set of strings of lengthk, each of whose is inΣExamples: Σ0:{?}, regardless of what alphabetΣis. That is?is the only string of length0IfΣ ={0,1}, then:

1.Σ1={0,1}

2.Σ2={00,01,10,11}

Note: confusion betweenΣandΣ1:

1.Σis an alphabet; its members0and1are symbols

2.Σ1is a set of strings; its members are strings (each one of length 1)

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 7/19

Kleen star

Σ?: The set of all strings over an alphabetΣ {0,1}?={?,0,1,00,01,10,11,000,...}Σ?= Σ0?Σ1?Σ2?... The symbol?is calledKleene starand is named after the mathematician and logician Stephen Cole Kleene.Σ+= Σ1?Σ2?...

Thus:Σ?= Σ+? {?}

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 8/19

Concatenation

Define the binary operation.calledconcatenationonΣ?as follows:

Ifa1a2a3...an

and b1b2...bm are inΣ?, then a1a2a3...an .b1b2...bm =a1a2a3...anb1b2...bm Thus, strings can be concatenated yielding another string: Ifxareybe strings thenx.ydenotes the concatenation ofxandy, that is, the string formed by making a copy ofxand following it by a copy ofyExamples:

1.x= 01101andy= 110

Thenxy= 01101110andyx= 11001101

2. For any stringw, the equations?w=w?=whold.

That is,?is theidentity for concatenation(when concatenated with any string it yields the other string as a result)IfSandTare subsets ofΣ?, then

S.T={s.t|s?S,t?T}

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 9/19

Languages

IfΣis an alphabet, andL?Σ?, thenLis a (formal)languageoverΣ.Language: A (possibly infinite) set of strings all of which are chosen from some

?A language overΣneed not include strings with all symbols ofΣ Thus, a language overΣis also a language over any alphabet that is a superset ofΣExamples:

Programming language C

Legal programs are a subset of the possible strings that can be formed from the alphabet of the language (a subset of ASCII characters)English or French Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 10/19

Other language examples

1. The language of all strings consisting ofn0s followed byn1s (n≥0):

{?,01,0011,000111,...}

2. The set of strings of0s and1s with an equal number of each:

{?,01,10,0011,0101,1001,...}

3.Σ?is a language for any alphabetΣ

4.∅, the empty language, is a language over any alphabet

5.{?}, the language consisting of only the empty string, is also a language over any

alphabet NOTE:∅ ?={?}since∅has no strings and{?}has one

6.{w|wconsists of an equal number of0and1}

7.{0n1n|n≥1}

8.{0i1j|0≤i≤j}

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 11/19

Important operators on languages: Union

Theunionof two languagesLandM, denotedL?M, is the set of strings that are in eitherL, orM, or both.

Example

IfL={001,10,111}andM={?,001}then

L?M={?,001,10,111}

Automata Theory, Languages and Computation - M´ırian Halfeld-Ferrari - p. 12/19

Important operators on languages:Concatenation

Theconcatenationof languagesLandM, denotedL.Mor justLM, is the set of strings that can be formed by taking any string inLand concatenating it with any string inM.

Example

IfL={001,10,111}andM={?,001}then

L.M={001,10,111,001001,10001,111001}

quotesdbs_dbs2.pdfusesText_3

[PDF] theory of quadratic equation

[PDF] theory of semiotics ferdinand de saussure pdf

[PDF] therapeutic drug monitoring pdf

[PDF] therapeutic drug monitoring ppt

[PDF] therapeutic drug monitoring principles

[PDF] therapeutic drug monitoring review

[PDF] thermal model of a house

[PDF] thermostat simulink

[PDF] thesis about british and american english

[PDF] thesis on android application development

[PDF] thesis outline example

[PDF] thirty years war essay question

[PDF] thirty years war essay thesis

[PDF] thirty years war political causes

[PDF] thirty years' war