AutoMata
Intro
What
Why:
- limit of computations
- programming tools: compilers, hardware design, text editor, communication protocols, program proofing.
- learn to think in a formal way about computing
Mathmematical models of computation
Machine Models:
- Finite automata
- pushdown automata
- turing machine
Finite Automata
A Finite Automaton (FA) is a 5-tuple
(Q,∑,δ, qs, F):
a finite set called the states.-Q
a finite set called the alphabet-∑
the transition function-δ
starting state-qs
accepting states-F
Group Theory:
- Sets - קבוצה
- Sequence - סדרה
- Tuples - ק-איה
- Cartesian Product- מכפלה קרטזית
Words & Languages
Letters & Alphabet
∑- Alphabet
σ- Letter
w - string\word(Finite numbers of letters from the alpabet)
ε - empty word
.#a(w)- number of occurences of a in a word
operations:
- Reverse
- sub-string
- prefix
- suffix
- concatination
Languages
L - set of words
∅ - empty lang (zero word)
∑* - all words under L
Types:
- Infinite languages
- Finite languages
Operations:
- reverse - reverse every word in lang
- concatenation (A·B)- word of A prefix. word of B suffix
- iteration- Concat lang's words with themself k times
- positive closure
- L* - Kleene closure - concat with itself from endless times
Others:
L^0 = ε תמיד מילה ריקה
FA complete(finite) - אוטומט סופי דטרמינסטי
if every letter has a uniuqe transaction (only one option for a letter in a node)
שפה רגולרית regular language
היא שפה שקיים אוטומט סופי שמקבל אותה
אוטומט לא דטרמינסטי- NDA
כל מה שצריך זה לפחות מצב אחד שהתקבל אצל האוטומט כדי להגיד שמילה שייכת לשפת האוטומט
נשים לב כי פונקציית המצבים היא בעצם הדבר השונה שכן מכילה קבוצה של מעבריים אפשריים
Regular Operation
איחוד
חיתוך
Complement משלים לשפה
Minus הפרש
חיסור בין שפות
Concatenation
נרוץ באוטומט L1 עד מצב מקבל ואז נחליט לרוץ באוטומט L2
צריך לנחש את תזמון הקפיצה לL2, ופה מתחיל אוטמט לא דטרמיניסטי NDA החדש
- נגדיר אוטומט לכל אחת מהשפות בנפרד
- נריץ על כל אחד מהאוטומטים מילה כלשהי w
- ניצור אוטומט מאוחד, product automaton, שהוא מכפלה קרטזית של שני האוטומטים.
- אם השפה מתקבלת לאחד מהאוטומטים לפחות אז המילה שייכת לאוטומט, כלומר OR ||
אם השפה מתקבלת בשני האוטומטים אז היא מקבלת כלומר AND &&
אוטומט M שזהה למקורי, רק שנחליף את המצבים המקבלים עם המצבים
הלא-מקבלים 
יכול להכיל אחד מהחוקים הבאים:
DFA vs. NFA
שקילות האוטומטים
כאשר מקבלים את בדיוק אותה השפה
Every NFA has an equivalent DFA
The e closer
Regular Expression
Operations
Hierarchy
Minimal Automaton
When there're no two equivalent states
Equivalent State
when they show the same behavior:
if (q,w) not belong to F the (p,w) is not belong as well.
And so as the opposite
Finding Equivalent States Algorithm
- Dividing the states into 2 groups (finite or not finite states)
- Splitting into groups while checking Iteration k compares to k+1.**
- Stop the moment k equivalent to k+1.**
- if two states finish in the same group ten they're equivalent
Every regular language has only a single minimal automaton
Infinite & Finite Language
If L is finite then L is regular
Infinite non-regular
click to edit
Finite Language
finite number of state
The Pumping Lemma
Used to prove that a language is NOT REGULAR
*CANNOTbe used prove that a language IS regular
Context Free
Context Free
Grammer
Common Notation
Context-Free Grammer
דקדוק חופשי הקשר