Theorems Flashcards
Theorem One
Every DFSA M has a total DFSA M’ recognizing the same language
How to use Theorem One
Sink State
Which Theorem is the one to make a DFSA total?
Theorem 1
Theorem Two
If language L is regular then language ¬L is also regular
How to use theorem two
Make Total + Invert final states
Which Theorem is the one to make a DFSA negative
Theorem Two
Theorem Three
If L1 and L2 are regular then L1∩L2 is regular. See notes for formal representation
How to use Theorem Three
Recreate M∩ by combining states of both automaton
Which Theorem is the theorem of AND/∩
Theorem Three
Theorem Four
For every DFSA M there exists NFSA M’ recognizing the same language
How to use Theorem 4
Make sure DFSA is total
Which is the theorem from DFSA to NFSA
Theorem 4
Theorem 5
For every NFSA M there exists a DFSA M’ with same language
How to use Theorem 5
Redraw NFSA but some states may be combinations of multiple states (if multiple transitions from some state with same string)
Which Theorem is for NFSA to DFSA
Theorem Five
Theorem Six
For every NSFA M there exists a corresponding 𝜏-NSFA M’ recognizing the same language
How to use Theorem Six
No steps needed
Which theorem is used to make NFSA into 𝜏-NFSA
Theorem 6
Theorem Seven
For every 𝜏-NFSA M there exists a NFSA M’ recognizing the same language
How to use Theorem Seven
Step 1: Add direct symbol transitions
Step 2: Add new final states
Step 3: Remove all 𝜏-transitions
Step 4: Remove redundant states
Which theorem makes a 𝜏-NFSA into a NFSA
Theorem Seven
Theorem Eight
For any 2 regular languages, L1∪L2 is regular.
How to use Theorem Eight
Make a new start state with a 𝜏 transition to L1 q0 and L2 q0
Which theorem is ∪/OR
Theorem Eight
Theorem Nine
if 2 regular languages exist then L1.L2 exists
How to use Theorem Nine
Final states of M1 link to start state of M2 with tao transition
Which is the theorem of language concatenation (.)
Theorem Nine
Theorem Ten
If L is regular, then L* is Regular
How to use Theorem Ten
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.
Which is the theorem of universal exponentiation (*)
Theorem 10
Theorem Eleven
e1 ≡ e2 implies 〚e1〛= 〚e2〛.
This also proves that Ø U〚e1〛= 〚e1〛and {E} .〚e1〛= 〚e1〛
Which is the theorem of soundness
Theorem 11
Theorem 12
For every regex e there exists a corresponding NFSA recognizing the some L.
〚e〛= L(M)
Which is the theorem stating that for all regex there exists a corresponding NFSA
Theorem 12
Theorem 13
For every DFSA M there exists a regular expression that recognizes the same language
Which theorem states that for every DFSA a corresponding regex exists
Theorem 13
Theorem 14
If a language is finite it is regular
Which theorem states that is a language is finite it is regular
Theorem 14
Theorem 15
If a DFSA M has n states, then if there is a string s accepted by M with length >= n it implies:
- M contains at least one loop which can be reached from q0 and F
- The language accepted by M is infinite
- a. len(s1s2) <= p
b. len(s2) >= 1
c. For all k>=0.s1(s2)^k.s3 E L
Which Theorem is of pumping lemma
Theorem 15
