TD 6 : Automates à pile

Énoncé

EX 1

1.

%3 q_0 q_0 q_0->q_0 c, ⊥/⊥ a a q_0->a a, A/AA    | b, A/𝜀 b b q_0->b b, B/BB    | b, B/𝜀 ⊥->q_0 a->q_0 𝜀, ⊥/⊥ b->q_0 𝜀, ⊥/⊥

2.

%17 q_3 q_3 q_0 q_0 ⊥->q_0 q_0->q_0 a, A/AA | a, ⊥/⊥A q_1 q_1 q_0->q_1 𝜀, */* q_2 q_2 q_0->q_2 𝜀, */* q_1->q_3 𝜀, ⊥/⊥ q_1->q_1 b, A/𝜀 q_2->q_3 𝜀, ⊥/⊥ q_2->q_2 b, A/B | b, B/𝜀

3.

Palindromes :

%35 q_1 q_1 q_1->q_1 a_1, A_1/𝜀 | ⋯ | a_n, A_n/𝜀 q_0 q_0 ⊥->q_0 q_0->q_1 𝜀, */* q_0->q_0 a_1, */*A_1 | ⋯ | a_n, */*A_n

Non-palindromes :

L3={uawbu~ab}{wau~}
%45 q_f q_f u u ⊥->u u->u a_1, */*A_1 | ⋯ | a_n, */*A_n w w u->w x, */*x u_tilde u_tilde u->u_tilde x, */* w->w x, */* w->u_tilde x, */𝜀 avec x≠* u_tilde->q_f 𝜀, ⊥/⊥ u_tilde->u_tilde x, x/𝜀

4.

Non-square words :

L3={w of odd }{uavubvab,|u|=|u|,|v|=|v|}

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

uavubv=ulength iavu length i+jbv length j

is of the form:

uawwbv=ulength iawlength iwlength jbv length j
%63 is_odd_1 is_odd_1 is_odd_2 is_odd_2 is_odd_1->is_odd_2 x, ⊥/⊥ q_f q_f v_n v v_n->q_f 𝜀, ⊥/⊥ v_n->v_n a, U/𝜀 v_0 v v_0->q_f 𝜀, ⊥/⊥ v_0->v_0 a, U/𝜀 is_odd_0 is_odd_0 ⊥->is_odd_0 u_a_0 u_a_0 ⊥->u_a_0 𝜀, ⊥/⊥ ⊥->⋯ 𝜀, ⊥/⊥ u_a_n u_a_n ⊥->u_a_n 𝜀, ⊥/⊥ is_odd_0->is_odd_1 x, ⊥/⊥ is_odd_2->is_odd_1 x, ⊥/⊥ u_a_0->u_a_0 x, */*U w_a_0 w_a_0 u_a_0->w_a_0 a_0, */* w_a_0->w_a_0 x, U/𝜀 w_prime_a_0 w_prime_a_0 w_a_0->w_prime_a_0 𝜀, ⊥/⊥ w_prime_a_0->v_0 x≠a_0, */* w_prime_a_0->w_prime_a_0 x, */*U ⋯->q_f u_a_n->u_a_n x, */*U w_a_n w_a_n u_a_n->w_a_n a_n, */* w_a_n->w_a_n x, U/𝜀 w_prime_a_n w_prime_a_n w_a_n->w_prime_a_n 𝜀, ⊥/⊥ w_prime_a_n->v_n x≠a_n, */* w_prime_a_n->w_prime_a_n x, */*U

EX 2

tq,zaq,z1znq,zaqt0,𝜀𝜀qt1,z1𝜀qt2,z1z2𝜀𝜀qtnq,z1zn QQ{qtit=(q,z,a,q,𝛾)𝛿,0i|𝛾|}

where qt|𝛾|q

𝛤𝛤 𝛿{(q,z,a,q,𝜀)𝛿}{(q,z,a,qt,𝜀)t=(q,z,a,q,𝛾)𝛿}{(qti,zi,𝜀,qti+1,zi+1)t=(q,z,a,q,z1zn)𝛿}

It can be shown by induction on the length of the run that for all q,qQ,𝛾,𝛾𝛤,w𝛴

q,𝛾𝒜wq,wq,𝛾𝒜wq,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 qR𝛾R through an automaton 𝒜KR that reckons KR.

%113 q_f q_f q q read_q_rev_0 read_q_rev_0 q->read_q_rev_0 q^R[0] read_q_rev_1 read_q_rev_1 read_q_rev_0->read_q_rev_1 q^R[1] read_q_rev_1->⋯ q^R[2] read_q_rev_n read_q_rev_n ⋯->read_q_rev_n q^R[n] read_𝛾 read_𝛾 read_q_rev_n->read_𝛾

Method 2:

  • B=P,𝛤Q,𝛥,p0,F s.t L(B)=K
  • 𝒜=Q×{0,1} is pnznpqqF true ?,𝛴,P×𝛤,q0,(p0,z0),F

The aim is to ensure the following property :

q0,z0wq,z1znq0,z0wq,(p1,z1)(pn,zn)

with p0z1znpn in B

and it is accepted when

pnznpqqF

(to have z1znqK)

bpn,zn,q={1 if pnznpqqF0 else  𝛿{(q,b),(p,z)a(q,bpn,zn,q),(p=p1,z1),,(pn,zn)q,z𝒜aq,z1,,zn and p=p1z1zn1pn in B}

Leave a comment