[PDF] [PDF] q1 q2 q3 a b b a a b - New Jersey Institute of Technology

View - Download [PDF] q1 q2 q3 a b b a a b - New Jersey Institute of Technology

Previous PDF

Next PDF

CS 341: Foundations of CS II

Marvin K. Nakayama

Computer Science Department

New Jersey Institute of Technology

Newark, NJ 07102

CS 341: Chapter 11-2

Chapter 1

Regular Languages

Contents

Finite Automata

Class of Regular Languages is Closed Under Some Operations•

Nondeterminism

Regular Expressions

Nonregular Languages

CS 341: Chapter 11-3

Introduction

Now introduce a simple model of a computer having a finite amount of memory.• This type of machine will be known as afinite-state machineor finite automaton.

Basic idea how a finite automaton works:

It is presented an input string

w over an alphabet ; i.e., w?Σ?

It reads in the symbols of

w from left to right, one at a time. After reading the last symbol, it indicates if it accepts or rejects the string. These machines are useful for string matching, compilers, etc. CS 341: Chapter 11-4Deterministic Finite Automata (DFA)

Example: State diagramof DFA with alphabet

Σ={a,b}

q 1q 2 q 3a b b a a,b •q 1 ,q 2 ,q3 are thestates. •q 1 is thestart stateas it has an arrow coming into it from nowhere. •q 2 is anaccept stateas it is drawn with a double circle.

CS 341: Chapter 11-5

Deterministic Finite Automata

q 1 q 2 q 3 a b b a a,b Edges tell how to move when in a state and a symbol from is read.

DFA is fedinput string

w?Σ . After reading last symbol of w if DFA is in an accept state, then string isacceptedotherwise, it isrejected.

Process the following strings over

Σ={a,b}

on above machine: abaa is accepted aba is rejected is rejected q 1 q 1 q 2 q 3 q 2 a b a a q 1 q 1 q 2 q 3 a b a q 1

CS 341: Chapter 11-6

Formal Definition of DFA

Definition:Adeterministic finite automaton(DFA) is a 5-tuple

M=(Q,Σ,δ,q

0 ,F), where 1. Q is afiniteset of states. 2. is an alphabet, and the DFA processes strings over 3.

δ:Q×Σ→Q

is thetransition function. defineslabeloneachedge. 4. q 0 ?Q is thestart state(orinitial state). 5. F?Q is the set ofaccept states(orfinal states). Remark:Sometimes refer to DFA as simply afinite automaton (FA).

CS 341: Chapter 11-7

Transition Function of DFA

q 1 q 2 q 3 a b b a a,b

Transition function

δ:Q×Σ→Q

works as follows: For each state and for each symbol of the input alphabet, the function tellswhich(one)statetogotonext.

Specifically, if

r?Q and ,then

δ(r, ?)

is the state that the DFA goes to when it is in state r and reads in , e.g.,

δ(q

2 ,a)=q 3

For each pair of state

r?Q and symbol there isexactly oneedge leaving r labeled with Thus, there is no choice in how to process a string.

So the machine isdeterministic.

CS 341: Chapter 11-8

Example of DFA

q 1 q 2 q 3 a b b a a,b

M=(Q,Σ,δ,q

1 ,F) with

•Q={q

1 ,q 2 ,q 3

•Σ={a,b}

•δ:Q×Σ→Q

is described as ab q 1 q 1 q 2 q 2 q 3 q 2 q 3 q 2 q 2 •q 1 is the start state

•F={q

2

CS 341: Chapter 11-9

How a DFA Computes

DFA is presented with an input string

w?Σ

DFA begins in the start state.

DFA reads the string one symbol at a time, starting from the left. The symbols read in determine the sequence of states visited.

Processing ends after the last symbol of

w has been read.

After reading the entire input string

if DFA ends in an accept state, then input string w isaccepted; otherwise, input string w isrejected.

CS 341: Chapter 11-10

Formal Definition of DFA Computation

Let

M=(Q,Σ,δ,q

0 ,F) be a DFA.

String

w=w 1 w 2

···w

n , where each w i and n≥0 Then M accepts w if there exists a sequence of states r 0 ,r 1 ,r 2 ,...,r n ?Q such that 1. r 0 =q 0 first state r 0 in the sequence is the start state of DFA; 2. r n ?F last state r n in the sequence is an accept state; 3.

δ(r

i ,w i+1 )=r i+1 for each i=0,1,2,...,n-1 sequence of states corresponds to valid transitions for string w r 0 r 1 r 2 r n-1 r n w 1 w 2 w n

CS 341: Chapter 11-11

Language of Machine

Definition:If

A is the set of all strings that machine M accepts, then we say

A=L(M)

is thelanguage of machine M ,and M recognizes A

If machine

M has input alphabet ,then

L(M)?Σ

Definition:A language isregularif it is recognized by some DFA.

CS 341: Chapter 11-12

Examples of Deterministic Finite Automata

Example:Consider the following DFA

M 1 with alphabet

Σ={0,1}

q 1 q 2 0 1 0 1

Remarks:

•010110

is accepted, but 0101
is rejected.

•L(M

1 is the language of strings over in which the total number of 1 "s is odd. Can you come up with a DFA that recognizes the language of strings overquotesdbs_dbs22.pdfusesText_28

[PDF] find a regular expression for the set {anbm:( n + m) is even}.

[PDF] find a regular grammar that generates the language l (aa* (ab+ a)*).

[PDF] find all complex solutions calculator

[PDF] find an inmate

[PDF] find coinbase account number

[PDF] find connected components in directed graph

[PDF] find death notices

[PDF] find degree of vertex in graph

[PDF] find my 1099 misc online

[PDF] find my twitter account

[PDF] find object type javascript

[PDF] find octagonal prism volume

[PDF] find perfect square trinomial calculator

[PDF] find the basic feasible solution

[PDF] find the density of seawater at a depth where the pressure is