É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"];
}


### 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$

Tags:

Updated: