TD 6 : Automates à pile

Énoncé

EX 1

1.

  digraph {
    rankdir=LR;
    q_0[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="c, ⊥/⊥"];
    q_0 -> a[label="a, A/AA
    | b, A/𝜀"];
    a -> q_0[label="𝜀, ⊥/⊥"];
    q_0 -> b[label="b, B/BB
    | b, B/𝜀"];
    b -> q_0[label="𝜀, ⊥/⊥"];
  }

2.

  digraph {
    rankdir=LR;
    q_3[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, A/AA | a, ⊥/⊥A"];
    q_0 -> q_1[label="𝜀, */*"];
    q_1 -> q_1[label="b, A/𝜀"];
    q_0 -> q_2[label="𝜀, */*"];
    q_2 -> q_2[label="b, A/B | b, B/𝜀"];
    q_1 -> q_3[label="𝜀, ⊥/⊥"];
    q_2 -> q_3[label="𝜀, ⊥/⊥"];
  }

3.

Palindromes :

  digraph {
    rankdir=TR;
    q_1[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a_1, */*A_1 | ⋯ | a_n, */*A_n"];
    q_0 -> q_1[label="𝜀, */*"];
    q_1 -> q_1[label="a_1, A_1/𝜀 | ⋯ | a_n, A_n/𝜀"];
  }

Non-palindromes :

\[L_3 = \lbrace uawb\widetilde{u} \mid a≠b \rbrace ∪ \lbrace wa\widetilde{u} \rbrace\] 
  digraph {
    rankdir=TR;
    q_f[shape="doublecircle"];
    ⊥ -> u;
    u -> u[label="a_1, */*A_1 | ⋯ | a_n, */*A_n"];
    u -> w[label="x, */*x"];
    u -> u_tilde[label="x, */*"];
    w -> w[label="x, */*"];
    w -> u_tilde[label="x, */𝜀 avec x≠*"];
    u_tilde -> u_tilde[label="x, x/𝜀"];
    u_tilde -> q_f[label="𝜀, ⊥/⊥"];
  }

4.

Non-square words :

\[L_3 = \lbrace w \text{ of odd }\rbrace \\ ∪ \lbrace \underbrace{u a v} \, \underbrace{u' b v'} \mid a≠b, \vert u \vert = \vert u' \vert, \vert v \vert = \vert v' \vert \rbrace\]

But it a bit impractical, let’s rather note that:

\[\underbrace{u a v} \, \underbrace{u' b v'} = \underbrace{u}_{\text{length } i}a \underbrace{v u'}_{\text{ length } i+j} b \underbrace{v'}_{\text{ length } j}\]

is of the form:

\[\underbrace{u a w} \, \underbrace{w' b v} = \underbrace{u}_{\text{length } i}a \underbrace{w}_{\text{length } i} \underbrace{w'}_{\text{length } j} b \underbrace{v'}_{\text{ length } j}\] 
  digraph {
    rankdir=LR;
    is_odd_1[shape="doublecircle"];
    q_f[shape="doublecircle"];
    v_n[label="v"];
    v_0[label="v"];
    ⊥ -> is_odd_0;
    is_odd_0 -> is_odd_1[label="x, ⊥/⊥"];
    is_odd_1 -> is_odd_2[label="x, ⊥/⊥"];
    is_odd_2 -> is_odd_1[label="x, ⊥/⊥"];
    ⊥ -> u_a_0[label="𝜀, ⊥/⊥"];
    u_a_0 -> u_a_0[label="x, */*U"];
    u_a_0 -> w_a_0[label="a_0, */*"];
    w_a_0 -> w_a_0[label="x, U/𝜀"];
    w_a_0 -> w_prime_a_0[label="𝜀, ⊥/⊥"];
    w_prime_a_0 -> w_prime_a_0[label="x, */*U"];
    w_prime_a_0 -> v_0[label="x≠a_0, */*"];
    v_0 -> v_0[label="a, U/𝜀"];
    v_0 -> q_f[label="𝜀, ⊥/⊥"];
    ⊥ -> ⋯[label="𝜀, ⊥/⊥"];
    ⋯ -> q_f;
    ⊥ -> u_a_n[label="𝜀, ⊥/⊥"];
    u_a_n -> u_a_n[label="x, */*U"];
    u_a_n -> w_a_n[label="a_n, */*"];
    w_a_n -> w_a_n[label="x, U/𝜀"];
    w_a_n -> w_prime_a_n[label="𝜀, ⊥/⊥"];
    w_prime_a_n -> w_prime_a_n[label="x, */*U"];
    w_prime_a_n -> v_n[label="x≠a_n, */*"];
    v_n -> v_n[label="a, U/𝜀"];
    v_n -> q_f[label="𝜀, ⊥/⊥"];
  }

EX 2

\[t ≝ q, z ⟶^a q, z_1 ⋯ z_n \\ ⇓ \\ q, z ⟶^a q_t^0, 𝜀 ⟶^𝜀 q_t^1, z_1 ⟶^𝜀 q_t^2, z_1 z_2 ⟶^𝜀 ⋯ ⟶^𝜀 q_t^n ≝ q', z_1 ⋯ z_n\] \[Q' ≝ Q \sqcup \lbrace q_t^i \mid t = (q, z, a, q', 𝛾) ∈ 𝛿, 0 ≤ i ≤ \vert 𝛾 \vert \rbrace\]

where $q_t^{\vert 𝛾 \vert} ≝ q’$

\[𝛤' ≝ 𝛤\] \[𝛿' ≝ \lbrace (q, z, a, q', 𝜀) ∈ 𝛿 \rbrace \\ ∪ \lbrace (q, z, a, q_t, 𝜀) \mid t = (q, z, a, q', 𝛾) ∈ 𝛿 \rbrace \\ ∪ \lbrace (q_t^i, z_i, 𝜀, q_t^{i+1}, z_{i+1}) \mid t = (q, z, a, q', z_1 ⋯ z_n) ∈ 𝛿 \rbrace\]

It can be shown by induction on the length of the run that for all $q, q’∈Q, 𝛾, 𝛾’∈𝛤^\ast, w∈𝛴^\ast$

\[q, 𝛾 ⟶^w_𝒜 q', w' ⟺ q, 𝛾 ⟶^w_{𝒜'} q', w'\]

Donc

\[L(𝒜) = L(𝒜')\]

EX 3

Method 1:

Out of each state $q$ of $𝒜$, $q$ is appended to the stack, and one reads the content of the stack $q^R𝛾^R$ through an automaton $𝒜_K^R$ that reckons $K^R$.

  digraph {
    rankdir=TR;
    q_f[shape="doublecircle"];
    q -> read_q_rev_0[label="q^R[0]"];
    read_q_rev_0 -> read_q_rev_1[label="q^R[1]"];
    read_q_rev_1 -> ⋯[label="q^R[2]"];
    ⋯ -> read_q_rev_n[label="q^R[n]"];
    read_q_rev_n -> read_𝛾;
  }

Method 2:

  • $B = ⟨P, 𝛤∪Q, 𝛥, p_0, F⟩$ s.t $L(B) = K$
  • $𝒜’ = ⟨Q × \underbrace{\lbrace 0, 1 \rbrace}_{\text{ is } p_n ⟶^{z_n} ⟶ p ⟶^q ⟶ q’∈F \text{ true ?}}, 𝛴, P \times 𝛤, q_0, (p_0, z_0), F’⟩$

The aim is to ensure the following property :

\[q_0, z_0 ⟶^w q, z_1 ⋯ z_n \\ q_0, z_0 ⟶^w q, (p_1, z_1) ⋯ (p_n, z_n)\]

with $p_0 ⟶^{z_1} ⟶ ⋯ ⟶^{z_n} p_n$ in $B$

and it is accepted when

\[p_n ⟶^{z_n} ⟶ p ⟶^q ⟶ q'∈F\]

(to have $z_1 ⋯ z_n q ∈ K$)

\[b_{p_n, z_n, q} = \begin{cases} 1 \text{ if } p_n ⟶^{z_n} ⟶ p ⟶^q ⟶ q'∈F \\ 0 \text{ else } \end{cases}\] \[𝛿 ≝ \lbrace (q, b), (p, z) ⟶^a (q', b_{p_n, z_n, q'}), (p=p_1, z_1), ⋯, (p_n, z_n) \mid q, z ⟶^a_𝒜 q', z_1, ⋯, z_n \text{ and } p=p_1 ⟶^{z_1} ⟶ ⋯ ⟶^{z_{n-1}} p_n \text{ in } B \rbrace\]

Leave a comment