Pumping lemma

Il pumping lemma è una cavolata, espressa in una maniera complicata perché formale.

Ogni stringa sposta l'automa da uno stato all'altro, ma se ci sono più lettere che stati è ovvio che perché la stringa sia riconosciuta bisogna che ripeta più volte il passaggio attraverso alcuni stati.

Gli angolofoni lo chiamano principio dei buchi della piccionaia, noi principio dei cassetti, ma il senso non cambia.

In pratica quindi:

  1. for each i ≥ 0, xyiz ∈ A significa che A contiene xz, xyz, xyyz, xyyyz, xyyyyz...
  2. |y| > 0 significa, banalmente, che non posso scegliere ε come y, cioè devo avere un y che contiene qualcosa. Al limite, lo ripeto zero volte...
  3. |xy| ≤ p significa che o p si ferma a x oppure è lungo almeno xy

Da questi tre punti si evince anche che:

  1. x e z possono essere ε
  2. se p > 0, allora o x o y devono essere diversi da ε

La struttura a livelli ISO/OSI

 

Nome Tipo di informazione scambiata Descrizione breve brevissima Alcuni protocolli della suite TCP/IP
Application APDU Usa i dati all'interno di un'applicazione. HTTP, SMTP, DNS, RTP
Presentation PPDU Trasforma i dati trasmessi in "oggetti" logici.
Session SPDU Questo livello permette di gestire le sessioni tra utenti.
Transport TPDU Questo livello "compone il puzzle" dei pacchetti, garantendo che non manchi niente. TCP, UDP
Network packet Questo livello determina come un'informazione viene instradata da una sorgente a una destinazione. IP, ICMP
Data Link frame Questo livello garantisce che i pacchetti non contengano errori di trasmissione. DSL, SONET, 802.11, Ethernet
Physical bit In questo livello si scambiano bit: ciò che questo livello fa è garantire che un bit che vale 1 per il sender valga 1 anche per il receiver e viceversa. Inoltre determina quando una connessione inizia e finisce e quale sarà il bitrate.

 

exercise 1.14

a. Theorem

Show that if M is a DFA that recognizes language B, swapping the accept and nonaccept states in M yields a new DFA recognizing the complement of B. Conclude that the class of regular languages is closed under complement.

a. Proof

This proof is based on induction.

Base case: a DFA with a single state, don't care what is the alphabet. Every letter brings to the only state. Obviously, if the state is an accepted state (F = {q0}), the DFA accepts every string; if the state is a non-accepted state (F = ∅), the DFA doesn't accept strings.

Inductive step: Let N a DFA that respect the theorem. If we add a new state Fnew, we must add an outgoing arrow for each letter and we can add some incoming arrow, moving them from other states.

Now, there are three cases: if the string ends before reaching Fnew, the theorem is proven, because the existence of Fnew isn't relevant. If the string ends at Fnew, the change of the acceptance of Fnew inverts the behavior of the DFA.

If the string ends at the state after Fnew, that we can name Fnew+1, the change of the acceptance of Fnew+1 inverts the behavior of the DFA.

After Fnew+1, we are again inside N, so the theorem is proved.

a. Proof (2)

For each string s, the membership of each state at F don't change the path that s follows. So, if s ends in an accepted state, the string is accepted, and changing this state the string isn't accepted anymore; and vice versa.

a. Conclusion

Let S a class of strings s composed by letters of Σ. Each string of s must belong to a regular language recognized by N or ¬N, since every state is accepted in N or ¬N.

Since "A language is called regular language if some finite automaton recognizes it" (Sipser, definition 1.16), all the languages that recognize every string s must be recognized by N or ¬N.

b. Theorem

Show by giving an example that if M is an NFA that recognizes language C, swapping the accept and nonaccept states in M doesn’t necessarily yield a new NFA that recognizes the complement of C. Is the class of languages recognized by NFAs closed under complement? Explain your answer.

b. Proof

A simple example is:

N = ({q0, q1}, {A, B}, δ, q0, {q0, q1})
δ = (q0, A) = q1

the string "B" is not recognized both by N and ¬N

Since every NFA have an equivalent DFA (Sipser, theorem 1.39), and the NFA is a special class of DFAs, the class of NFA is closed under complement.