1 / 46

# Limited Automata and Non Determinism .

29 views
Description
2. Definition 1.1: Finite Automaton. 3. State Diagram for M1. q3. q1. q2. . . . . . . . 0. 1. 1. 0. 0, 1. 4. Information Representation for M1. 5. Undertaking 01 DFA. Actualize M1 with your most loved programming language.GUITwo catches for info 0 and 1State graph with the present state highlighted. 6. Dialect of M1.
Transcripts
Slide 1

﻿Limited Automata and Non Determinism http://cis.k.hosei.ac.jp/~yukita/

Slide 2

Definition 1.1: Finite Automaton

Slide 3

State Diagram for M 1 0 q 3 q 1 q 2 1 0, 1

Slide 4

Data Representation for M 1

Slide 5

Task 01 DFA Implement M 1 with your most loved programming dialect. GUI Two catches for information 0 and 1 State graph with the present state highlighted

Slide 6

Language of M 1

Slide 7

State Diagram for M 5 0 q 1 0, <RESET> 2, <RESET> 0 1 2 q 0 q 2 1, <RESET>

Slide 8

Data Representation for M 5

Slide 9

Informal Description of M 5 M 5 keeps a running check of the entirety of the numerical images it peruses, modulo 3. Each time it gets the <RESET> image it resets the number to 0. M 5 acknowledges if the whole is 0, modulo 3.

Slide 10

Definition 1.7: Regular Language A dialect is known as a standard dialect if some limited robot remembers it.

Slide 11

Example 1.9: A limited robot E 2 E 2 perceives the consistent dialect of all strings that contain the string 001 as a substring. 0010, 1001, 001, and 1111110011110 are altogether acknowledged, yet 11 and 0000 are definitely not.

Slide 12

Find an arrangement of conditions of E 2 You haven\'t quite recently observed any images of the example, have recently observed a 0, have quite recently observed 00 or, have recently observed the whole example 001. Relegate the states q , q 0 , q 00 , and q 001 to these potential outcomes.

Slide 13

Draw a State Diagram for E 2 0, 1 0 q 0 q 0 q 00 q 001 1 0 1

Slide 14

Regular Operations on Languages

Slide 15

Example 1.11

Slide 16

Theorem 1.12 Closedness for Union

Slide 17

Proof of Theorem 1.12 Proof of Th 1.12

Slide 18

Construction of M Proof of Th 1.12

Slide 19

Correctness You ought to check the accompanying. For any string perceived by M 1 is perceived by M . For any string perceived by M 2 is perceived by M . For any string perceived by M is perceived by M 1 or M 2 . Confirmation of Th 1.12

Slide 20

Slide 21

Nondeterminism To demonstrate Theorem 1.13, we require nondeterminism. Nondeterminism is a speculation of determinism. Along these lines, each deterministic robot is consequently a nondeterministic machine.

Slide 22

Nondetermistic Finite Automata A nondeterministic limited robot can be not the same as a deterministic one in that for any info image, nondeterministic one can travel to more than one states. epsilon move NFA and DFA remain for nondeterministic limited robot and deterministic limited machine , individually.

Slide 23

NFA N 1 0,1 q 3 1 q 4 q 1 q 2 1 0, e

Slide 24

Parallel world and NFA ... ... acknowledge

Slide 25

Example 1.14 NFA N 2 0,1 q 3 q 4 q 1 q 2 0,1 1 0, 1 Let dialect A comprise of all strings over {0,1} containing a 1 in the third position from the end. N 2 perceives A .

Slide 26

A DFA equal to N 2 0 q 010 q 110 q 000 q 100 0 1 0 1 0 1 0 1 q 011 q 111 q 001 q 101 1

Slide 27

Example 1.15 NFA N 3 0 e 0 e 0 Let dialect A comprise of all strings 0 k , where k is a different of 2 or 3. N 3 perceives A .

Slide 28

A DFA proportionate to N 3 0, 1 q - 1 q 4 q 5 q 0 q １ q ２ q 3 0

Slide 29

Example 1.16 NFA N 4 q 1 a b e a q 3 q 2 a,b N 4 acknowledges e , a, baba , and baa . N 4 does not acknowledge b, nor babba .

Slide 30

Definition 1.17: NFA

Slide 31

0,1 1 0, e 1 q 3 q 4 q 1 q 2 Example 1.18 NFA N 1

Slide 32

In what circumstance is Non Determinism important? Von Neumann machines are deterministic. Notwithstanding, there are many situations where machine determination is all we require.

Slide 33

Theorem 1.19 Every nondeterministic limited robot has an equal deterministic limited machine. Def. The two machines are equal is they perceive a similar dialect.

Slide 34

Proof of Th. 1.19 Proof of Th 1.19

Slide 35

Incorporate e bolts Proof of Th 1.19

Slide 36

Corollary 1.20 A dialect is general if and just if some nondeterministic limited robot remembers it.

Slide 37

Example 1.21 NFA N 4 to DFA 1 b an e a 3 2 a,b

Slide 38

Task 02 Parallel World Write a program that reenacts N 4 . GUI Three catches for info 0, 1, and epsion. State graph that mirror the fanning of the world.

Slide 39

Start and Accept states

Slide 40

The state outline of D a,b a b {2} {1,2} f {1} a,b b a b an a {2,3} {1,2,3} {3} a {1,3} a b

Slide 41

Theorem 1.22 The class of standard dialects is shut under the union operation. N 1 e N 2

Slide 42

Proof of Th. 1.22

Slide 43

N 2 N 1 Theorem 1.23 The class of standard dialects is shut under the link operation. N e

Slide 44

Proof of Th. 1.23

Slide 45

N 1 Theorem 1.24 The class of standard dialects is shut under the star operation. N e

Slide 46

Proof of Th. 1.24

Recommended
View more...