Esercizi

• Regex e DFA dell'insieme $D$ di stringhe con numero pari di $a$, dispari di $b$ e che non contengono $ab$

  La regex sarà $R=b(bb{)}^{\ast }(aa{)}^{\ast }$, mentre il DFA:

  

• L'insieme $D$ di stringhe con lo stesso numero di $01$ e $10$ è regolare

  Questo è dimostrato perchè esiste un DFA che lo riconosce:

  

• Se $A$ è regolare allora lo è anche $\bar{A}=\left\{w|w\notin A\right\}$

  Essendo $A$ regolare esiste un DFA $D=(Q,\Sigma ,\delta ,q_0,F)$ per cui $L(B)=A$.

  Sia allora $D^{\prime }=(Q,\Sigma ,\delta ,q_0,Q\setminus F)$, da cui si conclude che $\forall w\in {\Sigma }^{\ast },w\in L(D)\iff w\notin L(D^{\prime })$ perchè gli invertire gli stati finali porta ad accettare tutte le stringhe che non sono in $A$.

• $F=\left\{ww|w\in \{0,1{\}}^{\ast }\right\}$ non è regolare

  Per assurdo $F$ è regolare, allora si usa $s=0^{p}10^{p}1\in A$ con $|s|=2p+2\ge p$.

  Dato che $s=xyz$, $|y|>0$ e $|xy|\le p$, si ha che la $y$ si trova nei primi $p$ zeri perchè $|xy|\le |0^p|=p$, quindi $x{y}^{2}z=0^{p+k}10^{p}1$ (con $k>0$ perchè $|y|>0$) non fa parte di $F$ e allora non è regolare.

• $A=\left\{0^n{1}^n|n\ge 0\right\}$ non è regolare

  Per assurdo $A$ è regolare, allora si sceglie $s=0^p{1}^p\in A$ perchè $|s|=2p\ge p$.

  Senza considerare che $|xy|\le p$, si ottiene che:

  • $y$ si trova negli $0$: $x{y}^{2}z=0^{p+k}{1}^p\notin A$
  • $y$ si trova negli $1$: $x{y}^{2}z=0^p{1}^{p+k}\notin A$
  • $y$ si trova tra entrambi gli $0$ e $1$: $x{y}^{2}z$ avrà degli $1$ prima degli $0$, e.g. $$\underset{x}{\underbrace{00}}\underset{y}{\underbrace{01}}\underset{z}{\underbrace{11}}\in A\Rightarrow \underset{x}{\underbrace{00}}\underset{y^2}{\underbrace{0101}}\underset{z}{\underbrace{11}}\notin A$$

• $A=\left\{a^{2^n}|n\ge 0\right\}$ non è regolare

  Per assurdo $A$ è regolare, allora si sceglie $s=a^{2^p}$ perchè $|s|=2^p\ge p$.

  Dato che $s=xyz$ con $|y|>0$ e $|xy|\le p$: $$2^p=|xyz|\underset{|y|>0}{\underbrace{<}}|x{y}^{2}z|\underset{|xy|\le p}{\underbrace{\le }}{2}^p+p<2^p+2^p=2^{p+1}$$ allora $2^p<|x{y}^{2}z|<2^{p+1}$ di conseguenza $x{y}^{2}z\notin A$ e $A$ non è regolare.

• $G=\left\{a{b}^n{c}^n|n\ge 0\right\}$ non è regolare

  Per assurdo $G$ è regolare, allora si usa $s=a{b}^p{c}^p$ perchè $|s|=2p+1\ge p$.

  Siccome $s=xyz$ con $|y|>0$ e $|xy|\le p$, si ha che:

  • $a$ è in $y$: $x{y}^{2}z\notin G$ perchè contiene due $a$
  • $a$ non è in $y$: $y$ contiene solo $b$ perchè $|xy|=|ay|\le p$ e quindi $x{y}^{2}z=a{b}^{p+k}{c}^p\notin G$

• $F=\left\{a^i{b}^j{c}^k|i,j,k\ge 0\wedge (i=1\Rightarrow j=k)\right\}$ non è regolare

  Per assurdo $F$ è regolare.

  Usando l'esercizio precedente si può notare che $G=F\cap a{b}^{\ast }{c}^{\ast }$, allora siccome sia $F$ (per ipotesi) che $a{b}^{\ast }{c}^{\ast }$ sono regolari anche $G$ deve esserlo per chiusura dell'intersezione, che è assurdo.