Luglio 2019 Archive

Un linguaggio regolare finito riconosce un insieme finito di stringhe.

Posso costruire un automa sotto forma di albero in cui il percorso più lungo corrisponde alla stringa più lunga.

Quindi è possibile costruire un automa il cui numero massimo di stati è la lunghezza della stringa più lunga per il numero di lettere.

Un linguaggio finito è sempre regolare (senza loop).

Un linguaggio con loop è non regolare se contraddice il pumping lemma.

Un linguaggio con loop che rispetta il pumping lemma può essere o non essere regolare.

https://www.geeksforgeeks.org/theory-of-computation-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, xyⁱz ∈ 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 ε

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 = {q₀}), 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 F_new, 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 F_new, the theorem is proven, because the existence of F_new isn't relevant. If the string ends at F_new, the change of the acceptance of F_new inverts the behavior of the DFA.

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

After F_new+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 = ({q₀, q₁}, {A, B}, δ, q₀, {q₀, q₁})
δ = (q₀, A) = q₁

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.