• Head of the development team @ LIPN • Lecturer (65 hrs) @ École SupGalilée ◦ Software Engineering and OOP courses • Member @ Software/Source Codes College • Ambassador @ Software Heritage • Author of 31 publications (5 journal articles) You can find me at: ͐ [email protected] Ì www.jaime-arias.fr Jaime Arias Computability and Complexity 2/24
model systems that can be in different states and can change state based on some input. Example (Mario Bros) • Mario can be in different states e.g. walking, jumping, or attacking Jaime Arias Computability and Complexity 3/24
model systems that can be in different states and can change state based on some input. Example (Mario Bros) • Mario can be in different states e.g. walking, jumping, or attacking • Mario’s state changes based on player input e.g. pressing a button to jump Jaime Arias Computability and Complexity 3/24
of only finitely many states and transitions among them is called a finite-state transition system. • These systems can be modelled abstractly by a mathematical model called a finite automaton. Jaime Arias Computability and Complexity 4/24
Graphical Representation Implementation 2. Regular Languages Strings Extending the Transition Function Formal Definition Jaime Arias Computability and Complexity 5/24
(DFA) is the quintuple: A = ⟨ Q , Σ , , , ⟩ states input alphabet • Q is a finite set of states; • Σ is a finite set of symbols; Jaime Arias Computability and Complexity 7/24
(DFA) is the quintuple: A = ⟨ Q , Σ , δ , , ⟩ states input alphabet transition function • Q is a finite set of states; • Σ is a finite set of symbols; • δ : Q × Σ → Q is a transition function; Jaime Arias Computability and Complexity 7/24
(DFA) is the quintuple: A = ⟨ Q , Σ , δ , q0 , ⟩ states input alphabet transition function initial state • Q is a finite set of states; • Σ is a finite set of symbols; • δ : Q × Σ → Q is a transition function; • q0 ∈ Q is the initial state; and Jaime Arias Computability and Complexity 7/24
(DFA) is the quintuple: A = ⟨ Q , Σ , δ , q0 , F ⟩ states input alphabet transition function initial state final states • Q is a finite set of states; • Σ is a finite set of symbols; • δ : Q × Σ → Q is a transition function; • q0 ∈ Q is the initial state; and • F ⊆ Q is a set of final states. Jaime Arias Computability and Complexity 7/24
finite-length sequence of elements of Σ. • The length of a string s, denoted by |s|, is the number of symbols in s. Jaime Arias Computability and Complexity 12/24
finite-length sequence of elements of Σ. • The length of a string s, denoted by |s|, is the number of symbols in s. s = a a b a b where Σ = {a, b} |s| = 5 Jaime Arias Computability and Complexity 12/24
finite-length sequence of elements of Σ. • The length of a string s, denoted by |s|, is the number of symbols in s. s = a a b a b where Σ = {a, b} |s| = 5 • The empty string (ϵ) is the unique string of length 0, i.e. |ϵ| = 0. Jaime Arias Computability and Complexity 12/24
finite-length sequence of elements of Σ. • The length of a string s, denoted by |s|, is the number of symbols in s. s = a a b a b where Σ = {a, b} |s| = 5 • The empty string (ϵ) is the unique string of length 0, i.e. |ϵ| = 0. • The set of all strings over Σ is denoted by Σ∗. {a, b}∗ = {ϵ, a, b, aa, ab, ba, bb, aa, aaa, aab, . . . } Jaime Arias Computability and Complexity 12/24
finite-length sequence of elements of Σ. • The length of a string s, denoted by |s|, is the number of symbols in s. s = a a b a b where Σ = {a, b} |s| = 5 • The empty string (ϵ) is the unique string of length 0, i.e. |ϵ| = 0. • The set of all strings over Σ is denoted by Σ∗. {a, b}∗ = {ϵ, a, b, aa, ab, ba, bb, aa, aaa, aab, . . . } • Note: If Σ is nonempty, then Σ∗ is an infinite set of finite-length strings. Jaime Arias Computability and Complexity 12/24
a move from one state to another when a single symbol is given (i.e. δ). Let’s extend this to a string of symbols Jaime Arias Computability and Complexity 13/24
Transition Function: δ∗ : Q × Σ∗ → Q Formally, we can define δ∗ recursively as follows: δ∗(q, ϵ) def = q δ∗(q, sa) def = δ(δ∗(q, s), a) for all q ∈ Q, s ∈ Σ∗, and a ∈ Σ. Jaime Arias Computability and Complexity 15/24
a DFA A string s ∈ Σ∗ is accepted or recognized by a DFA A iff it takes the initial state q0 to a final state. That is: δ∗(q0, s) ∈ F Jaime Arias Computability and Complexity 19/24
a DFA A string s ∈ Σ∗ is accepted or recognized by a DFA A iff it takes the initial state q0 to a final state. That is: δ∗(q0, s) ∈ F q1 q2 0 1 1 0 s = 0 1 1 Jaime Arias Computability and Complexity 19/24
a DFA A string s ∈ Σ∗ is accepted or recognized by a DFA A iff it takes the initial state q0 to a final state. That is: δ∗(q0, s) ∈ F q1 q2 0 1 1 0 s = 0 1 1 ✓ Jaime Arias Computability and Complexity 19/24
a DFA A string s ∈ Σ∗ is accepted or recognized by a DFA A iff it takes the initial state q0 to a final state. That is: δ∗(q0, s) ∈ F q1 q2 0 1 1 0 0 s = 0 1 1 0 Jaime Arias Computability and Complexity 19/24
a DFA A string s ∈ Σ∗ is accepted or recognized by a DFA A iff it takes the initial state q0 to a final state. That is: δ∗(q0, s) ∈ F q1 q2 0 1 1 0 0 s = 0 1 1 0 Jaime Arias Computability and Complexity 19/24
a DFA The language accepted or recognized by a DFA A is the set of all strings accepted by A. That is: L(A) def = {s ∈ Σ∗ | δ∗(q0, s) ∈ F} Jaime Arias Computability and Complexity 22/24
a DFA The language accepted or recognized by a DFA A is the set of all strings accepted by A. That is: L(A) def = {s ∈ Σ∗ | δ∗(q0, s) ∈ F} q1 q2 0 1 1 0 L(A) = {1, 01, 11, 011, 01001, . . . } Jaime Arias Computability and Complexity 22/24
a DFA The language accepted or recognized by a DFA A is the set of all strings accepted by A. That is: L(A) def = {s ∈ Σ∗ | δ∗(q0, s) ∈ F} q1 q2 0 1 1 0 L(A) = {1, 01, 11, 011, 01001, . . . } = {s ∈ {0, 1}∗ | s ends in a 1} Jaime Arias Computability and Complexity 22/24
are equivalent iff they accept the same language L(A1) = L(A2) Regular Language A language L is called a regular language iff some DFA A recognizes it L = L(A) Jaime Arias Computability and Complexity 23/24
himito
fufufukakaka
trafficbrain
karakurist
ontheslope
culturaltransition
kanekomasahiro
koide3
mela_dayo
ozekinote
analokmaus
tomoyanonymous
techseoconnect
stephenakadiri
csswizardry
chriscoyier
orderedlist
codingconduct
tmiket
nonsquared
rkaga
addyosmani
![Computability and Complexity Jaime Arias [email protected]](https://files.speakerdeck.com/presentations/10e883c7297c45f59ff395a9ef32bbed/slide_0.jpg){kind=link}
![Computability and Complexity Jaime Arias [email protected]](https://files.speakerdeck.com/presentations/10e883c7297c45f59ff395a9ef32bbed/slide_65.jpg){kind=link}