Limited Automata.


88 views
Uploaded on:
Category: General / Misc
Description
Limited Automata. Limited Machine. Info. String. Yield. "Acknowledge" or "Reject". Limited Machine. Move Chart. introductory state. tolerating state. move. state. Starting Design. Info String. Perusing the Info. Info wrapped up. acknowledge. Dismissal.
Transcripts
Slide 1

Limited Automata

Slide 2

Finite Automaton Input String Output “Accept” or “Reject” Finite Automaton

Slide 3

Transition Graph starting state tolerating state move state

Slide 4

Initial Configuration Input String

Slide 5

Reading the Input

Slide 9

Input completed acknowledge

Slide 10

Rejection

Slide 14

Input completed reject

Slide 15

Another Rejection

Slide 16

reject

Slide 17

Another Example

Slide 21

Input completed acknowledge

Slide 22

Rejection Example

Slide 26

Input completed reject

Slide 27

Languages Accepted by FAs FA Definition: The dialect contains all data strings acknowledged by = { strings that convey to a tolerant state}

Slide 28

Example acknowledge

Slide 29

Example acknowledge

Slide 30

Example trap state acknowledge

Slide 31

Formal Definition Finite Automaton (FA) : set of states : info letters in order : move capacity : beginning state : set of tolerating states

Slide 32

Input Alphabet

Slide 33

Set of States

Slide 34

Initial State

Slide 35

Set of Accepting States

Slide 36

Transition Function

Slide 40

Transition Function

Slide 41

Extended Transition Function

Slide 45

Observation: if there is a stroll from to with mark then

Slide 46

Example: There is a stroll from to with name

Slide 47

Recursive Definition

Slide 49

Language Accepted by FAs For a FA Language acknowledged by :

Slide 50

Observation Language rejected by :

Slide 51

Example = { all strings with prefix } acknowledge

Slide 52

Example = { all strings without substring }

Slide 53

Example

Slide 54

Regular Languages Definition: A dialect is general if there is FA such that Observation: All dialects acknowledged by FAs shape the group of standard dialects

Slide 55

Examples of normal dialects: { all strings with prefix } { all strings without substring } There exist automata that acknowledge these Languages (see past slides).

Slide 56

There exist dialects which are not Regular: Example: There is no FA that acknowledges such a dialect (we will demonstrate this later in the class)

Slide 57

.