Theorems

Question 1

Theorem One

Answer 1

Every DFSA M has a total DFSA M’ recognizing the same language

Question 2

How to use Theorem One

Answer 2

Sink State

Question 3

Which Theorem is the one to make a DFSA total?

Answer 3

Theorem 1

Question 4

Theorem Two

Answer 4

If language L is regular then language ¬L is also regular

Question 5

How to use theorem two

Answer 5

Make Total + Invert final states

Question 6

Which Theorem is the one to make a DFSA negative

Answer 6

Theorem Two

Question 7

Theorem Three

Answer 7

If L1 and L2 are regular then L1∩L2 is regular. See notes for formal representation

Question 8

How to use Theorem Three

Answer 8

Recreate M∩ by combining states of both automaton

Question 9

Which Theorem is the theorem of AND/∩

Answer 9

Theorem Three

Question 10

Theorem Four

Answer 10

For every DFSA M there exists NFSA M’ recognizing the same language

Question 11

How to use Theorem 4

Answer 11

Make sure DFSA is total

Question 12

Which is the theorem from DFSA to NFSA

Answer 12

Theorem 4

Question 13

Theorem 5

Answer 13

For every NFSA M there exists a DFSA M’ with same language

Question 14

How to use Theorem 5

Answer 14

Redraw NFSA but some states may be combinations of multiple states (if multiple transitions from some state with same string)

Question 15

Which Theorem is for NFSA to DFSA

Answer 15

Theorem Five

Question 16

Theorem Six

Answer 16

For every NSFA M there exists a corresponding 𝜏-NSFA M’ recognizing the same language

Question 17

How to use Theorem Six

Answer 17

No steps needed

Question 18

Which theorem is used to make NFSA into 𝜏-NFSA

Answer 18

Theorem 6

Question 19

Theorem Seven

Answer 19

For every 𝜏-NFSA M there exists a NFSA M’ recognizing the same language

Question 20

How to use Theorem Seven

Answer 20

Step 1: Add direct symbol transitions
Step 2: Add new final states
Step 3: Remove all 𝜏-transitions
Step 4: Remove redundant states

Question 21

Which theorem makes a 𝜏-NFSA into a NFSA

Answer 21

Theorem Seven

Question 22

Theorem Eight

Answer 22

For any 2 regular languages, L1∪L2 is regular.

Question 23

How to use Theorem Eight

Answer 23

Make a new start state with a 𝜏 transition to L1 q0 and L2 q0

Question 24

Which theorem is ∪/OR

Answer 24

Theorem Eight

Question 25

Theorem Nine

Answer 25

if 2 regular languages exist then L1.L2 exists

Question 26

How to use Theorem Nine

Answer 26

Final states of M1 link to start state of M2 with tao transition

Question 27

Which is the theorem of language concatenation (.)

Answer 27

Theorem Nine

Question 28

Theorem Ten

Answer 28

If L is regular, then L* is Regular

Question 29

How to use Theorem Ten

Answer 29

1) Make new start state (which is also final) transitioning to old start state with 𝜏.
2) Add 𝜏-transitions from final state to old start state.

Question 30

Which is the theorem of universal exponentiation (*)

Answer 30

Theorem 10

Question 31

Theorem Eleven

Answer 31

e1 ≡ e2 implies 〚e1〛= 〚e2〛.

This also proves that Ø U〚e1〛= 〚e1〛and {E} .〚e1〛= 〚e1〛

Question 32

Which is the theorem of soundness

Answer 32

Theorem 11

Question 33

Theorem 12

Answer 33

For every regex e there exists a corresponding NFSA recognizing the some L.

〚e〛= L(M)

Question 34

Which is the theorem stating that for all regex there exists a corresponding NFSA

Answer 34

Theorem 12

Question 35

Theorem 13

Answer 35

For every DFSA M there exists a regular expression that recognizes the same language

Question 36

Which theorem states that for every DFSA a corresponding regex exists

Answer 36

Theorem 13

Question 37

Theorem 14

Answer 37

If a language is finite it is regular

Question 38

Which theorem states that is a language is finite it is regular

Answer 38

Theorem 14

Question 39

Theorem 15

Answer 39

If a DFSA M has n states, then if there is a string s accepted by M with length >= n it implies:

1. M contains at least one loop which can be reached from q0 and F
2. The language accepted by M is infinite
3. a. len(s1s2) <= p
   b. len(s2) >= 1
   c. For all k>=0.s1(s2)^k.s3 E L

Question 40

Which Theorem is of pumping lemma

Answer 40

Theorem 15