profile pic
⌘ '
raccourcis clavier
Search

Deterministic Finite Automata

  • Étiquette

    • publié à

    • modifié à

    • durée

      4 min de lecture

    • source

      llms.txt

    definition

    Σ∗:set of all strings based off Σ\Sigma^{*}: \text{set of all strings based off }\Sigma DFAM=(Q,Σ,δ,s,F) Q:finite set of states Σ:finite alphabet δ:Q×Σ→Q→δ:Q×Σ→Q s:start state,s∈Q F:set of final states,F⊆Q \begin{align*} \text{DFA}\quad M &= (Q, \Sigma, \delta, s, F) \\\ Q &: \text{finite set of states} \\\ \Sigma &: \text{finite alphabet} \\\ \delta &: Q \times \Sigma \rightarrow Q \rightarrow \delta: Q \times \Sigma \rightarrow Q \\\ s &: \text{start state},\quad s\in{Q} \\\ F &: \text{set of final states},\quad F\subseteq{Q} \\\ \end{align*}

    examples

    Ex: Σ={a,b}\Sigma = \{a, b\}. Creates a DFA MM that accepts all strings that contains at least three a’s.

    Q={s1,s2,s3,s4} s=1 F={s4} \begin{align*} Q &= \{s_1, s_2, s_3, s_4\} \\\ s &= 1 \\\ F &= \{s_4\} \\\ \end{align*}

    Transition function:

    δ(1,a)=s2 δ(1,b)=s1 δ(2,a)=s3 δ(2,b)=s2 δ(3,a)=s4 δ(3,b)=s3 δ(4,a)=δ(4,b)=s4 \begin{align*} \delta(1, a) = s_2 \\\ \delta(1, b) = s_1 \\\ \delta(2, a) = s_3 \\\ \delta(2, b) = s_2 \\\ \delta(3, a) = s_4 \\\ \delta(3, b) = s_3 \\\ \delta(4, a) = \delta(4, b) = s_4 \\\ \end{align*}

    representation:

    stateDiagram-v2
    direction LR
    classDef accepting fill:#4CAF50,stroke:#333,stroke-width:2px
    classDef start fill:#FFD700,stroke:#333,stroke-width:2px

    s1: s1
    s2: s2
    s3: s3
    s4: s4

    [*] --> s1
    s1 --> s1: b
    s1 --> s2: a

    s2 --> s2: b
    s2 --> s3: a

    s3 --> s3: b
    s3 --> s4: a

    s4 --> s4: a,b

    class s4 accepting
    class s1 start

    if in final string then accept, otherwise reject the string

    language.

    Language of machine L(M)\mathcal{L}(M) is the set of strings M accepts, such that L(M)∈Σ∗\mathcal{L}(M) \in \Sigma^{*}

    L(M)={w∈Σ∗∣δ(s,w)∈F}\mathcal{L}(M) = \{w \in \Sigma^{*} | \delta(s, w) \in F\}

    Assumption: Σ={a,b}\Sigma = \{a, b\}

    Questions

    Find DFA MM such that L(M)=\mathcal{L}(M)= the following

    1. {xab∣x∈Σ∗}\{ xab \mid x \in \Sigma^{*} \}
    2. {x∣∣x∣%2=0}\{ x \mid |x| \% 2 = 0 \}
    3. {x∣x=2n , n∈N}\{ x \mid x = 2^n\space ,\space n \in \mathbb{N} \}, Σ={0,1}\Sigma = \{0, 1\}
    4. {x∣"abc"∈x}\{ x \mid "abc" \in x \}, Σ={a,b,c}\Sigma = \{a, b, c\}
    5. {x∣a is the second last char of x}\{ x \mid \text{a is the second last char of x} \}
    6. {an⋅bn∣n≥0}\{ a^n \cdot b^n \mid n \ge 0 \}
    7. {x∣a is the fifth last char of x}\{ x \mid \text{a is the fifth last char of x} \}
    stateDiagram-v2
    direction LR
    classDef accepting fill:#4CAF50,stroke:#333,stroke-width:2px
    classDef start fill:#FFD700,stroke:#333,stroke-width:2px

    s0: q0
    s1: q1
    s2: q2

    [*] --> s0
    s0 --> s0: b
    s0 --> s1: a
    s1 --> s0: a
    s1 --> s2: b
    s2 --> s0: a
    s2 --> s1: b

    class s2 accepting
    class s0 start

    stateDiagram-v2
    direction LR
    classDef accepting fill:#4CAF50,stroke:#333,stroke-width:2px
    classDef start fill:#FFD700,stroke:#333,stroke-width:2px

    s0: q0
    s1: q1

    [*] --> s0
    s0 --> s1: a,b
    s1 --> s0: a,b

    class s0 accepting
    class s0 start

    stateDiagram-v2
    direction LR
    classDef accepting fill:#4CAF50,stroke:#333,stroke-width:2px
    classDef start fill:#FFD700,stroke:#333,stroke-width:2px
    classDef dead fill:#ff6b6b,stroke:#333,stroke-width:2px

    s0: q0
    s1: q1
    s2: q2
    s3: dead

    [*] --> s0
    s0 --> s3: 0
    s0 --> s1: 1

    s1 --> s2: 0
    s1 --> s3: 1

    s2 --> s2: 0
    s2 --> s3: 1

    s3 --> s3: 0,1

    class s1 accepting
    class s0 start
    class s3 dead

    stateDiagram-v2
    direction LR
    classDef accepting fill:#4CAF50,stroke:#333,stroke-width:2px
    classDef start fill:#FFD700,stroke:#333,stroke-width:2px
    
    s0: q0
    s1: q1
    s2: q2
    s3: q3
    
    [*] --> s0
    
    s0 --> s0: b,c
    s0 --> s1: a
    
    s1 --> s0: a,c
    s1 --> s2: b
    
    s2 --> s0: a,b
    s2 --> s3: c
    
    s3 --> s3: a,b,c
    
    class s3 accepting
    class s0 start

    stateDiagram-v2
    direction LR
    classDef accepting fill:#4CAF50,stroke:#333,stroke-width:2px
    classDef start fill:#FFD700,stroke:#333,stroke-width:2px
    
    s0: q0
    s1: q1
    s2: q2
    s3: q3
    
    [*] --> s0
    
    s0 --> s0: a,b
    s0 --> s1: a
    
    s1 --> s2: b
    s1 --> s3: a
    
    s2 --> s0: a,b
    s3 --> s0: a,b
    
    class s2 accepting
    class s0 start

    non-regular.

    proof using Pumping Lemma

    • assume the language is regular, let pp be the pumping length.
    • Consider string s=an⋅bns = a^n \cdot b^n
    • any way of diving s=xyzs=xyz where ∣xy∣≤p\mid xy \mid \le p and ∣y∣≥0\mid y \mid \ge 0 will results y contains only a’
    • pumped wouldn’t be in the language q.e.d
    stateDiagram-v2
    direction LR
    classDef accepting fill:#4CAF50,stroke:#333,stroke-width:2px
    classDef start fill:#FFD700,stroke:#333,stroke-width:2px
    
    s0: q0
    s1: q1
    s2: q2
    s3: q3
    s4: q4
    s5: q5
    
    [*] --> s0
    
    s0 --> s0: a,b
    s0 --> s1: a
    
    s1 --> s2: a,b
    s2 --> s3: a,b
    s3 --> s4: a,b
    s4 --> s5: a,b
    s5 --> s0: a,b
    
    class s5 accepting
    class s0 start

    Vous pourriez aimer ce qui suit

  • Databases
  • SVCCA
  • NVF for affordable housing
  • cyanotype
  • pdfs.
  • reductionism
  • PID Controller
    • constrained decoding
    structured generations in vLLM a la carte
    Automata
    Book: pdf Q1: T/F, if F explain why. Q4: regular expression, 5 separate q Q2/Q3: DFAs and NFAs Product construction: \cap \cup of DFAs Subset construction: NFA to DFA Quotient construction: State minimization Set theory Complement in \Sigma^{*}: \overline{L} = \Sigma^{*} - L associative: \begin{align*} (A \cup B) \cup C &= A \cup (B \cup C), \\ (A \cap B) \cap C &= A \cap (B \cap C), \\ (AB)C &= A(BC).