Ejercicios para la evaluación continua

Tema 5: No regularitat. Autòmats amb pila i jerarquia de Chomsky

Leyenda

= el ejercicio ha sido asignado a un/una estudiante/a y será resuelto en clase.
Para ver la asignación (y la fecha de entrega) consulta el racó.

No regularitat

Ejercicio 1 Demostreu la no-regularitat dels següents llenguatges:

\{a^nb^n\ |\ n\in\dot{2}\}.
\{a^nb^n\ |\ n\in\dot{3}\}.
\{a^nb^m\ |\ n\not=m\}.
\{a^{2n}b^n\ |\ n\in\dot{2}\}.
\{w\in\{a,b\}^*\ |\ \;|w|_a=|w|_b\}.
\{a^nb^m\ |\ n\leq m\}.
\{a^nb^m\ |\ n\geq m\}.
\{c^ma^nb^n\ |\ (n,m\geq 0)\}.
\{a,b\}^*\cup\{c^ma^nb^n\ |\ (m\geq 1)\wedge(n\geq 0)\}.
\{w\in\{a,b\}^*\ |\ w=w^R\}.
\{ww\in\{a,b\}^*\}
\{a^{n^2}\ |\ n\geq 0\}.
\{a^{2^n}\ |\ n\geq 0\}.
\{a^n\ |\ n\text{ apareix a la successió de Fibonacci}\}.
\{a^n\ |\ n\text{ és primer}\}.
\{a^n\ |\ n\text{ és parell o primer}\}.
\{abab^2ab^3\ldots ab^n\ |\ n\geq 0\}.
\{w_1\#w_2\ |\ w_1,w_2\in\{0,1\}^*\wedge (|w_1|<|w_2|\vee |w_1|\in\dot{2})\}.
\{u\#v\ |\ u,v\in\{a,b\}^*\wedge v\text{ és submot de }u\}.
\{w\in(a+b+c)^*\ |\ |w|_a\geq |w|_b\vee |w|_b\geq|w|_c\}.
Qualsevol subconjunt infinit del llenguatge \{a^nb^n\}.
\{w\in\{a,b\}^*\ |\ (|w|\in\dot{3}\Rightarrow |w|_a=|w|_b)\}.
\{w_1\#w_2\ |\ w_1,w_2\in\{0,1\}^*\wedge \mathtt{valor}_2(w_1)=\mathtt{valor}_2(w_2)\}.
\{w_1\#w_2\ |\ w_1,w_2\in\{0,1\}^*\wedge \mathtt{valor}_2(w_1)=1+\mathtt{valor}_2(w_2)\}.
\{w_1\#w_2\#w_3\ |\ w_1,w_2,w_3\in\{0,1\}^*\wedge \mathtt{valor}_2(w_1)+\mathtt{valor}_2(w_2)=\mathtt{valor}_2(w_3)\}.
\{xy\in\{a,b\}^*\mid |x|_a=2|y|_b\}

Ejercicio 2 Considerem el llenguatge L_k=\{w\in(0+1)^*\ |\ \mathtt{valor}_2(w)\leq k\}. Quins dels següents llenguatges són regulars per a qualsevol k:

L_k.
\bigcup_{k\geq 1}L_k.
\{w\#w\ |\ w\in L_k\}.
\{1w\#1w\ |\ 1w\in L_k\}.
\{1w\#1w\ |\ w\in L_k\}.
\{w\#w\ |\ w\in L_k\;\wedge\;|w|\leq\mathtt{valor}_2(w)\}.
\{w\#w\ |\ 1w\in L_k\}.
\{w_1\#w_2\ |\ w_1,w_2\in L_k\wedge \mathtt{valor}_2(w_1)=\mathtt{valor}_2(w_2)\}.
\{w_1\#w_2\ |\ \exists k:(w_1,w_2\in L_k\;\wedge\;\mathtt{valor}_2(w_1)=\mathtt{valor}_2(w_2))\}.

Ejercicio 3 Quins dels següents llenguatges podem assegurar que són no-regulars sabent que A i B són no-regulars i que \sigma és un morfisme.

\bar{A}.
A\cup B.
A\cap B.
A\cdot B.
A^R.
A^*.
S(A) (recordeu la definició de shiftar un llenguatge dels exercicis del primer tema).
\sigma(A).
\sigma^{-1}(A).

Ejercicio 4 Determineu quin llenguatge genera cadascuna de les següents CFG’s, i justifiqueu si aquest llenguatge és regular o no.

S \to AB\ |\ CD\\ A \to 0A0\ |\ 0\\ B \to 1B1\ |\ \lambda\\ C \to 0C0\ |\ \lambda\\ D \to 1D1\ |\ \lambda
S \to aA\ |\ bB\ |\ \lambda\\ A \to Sa\ |\ Sb\\ B \to Sb
S \to AB\\ A \to 0A0\ |\ 1\\ B \to 1B1\ |\ 0
S \to 0S0\ |\ 0S1\ |\ \lambda
S \to AB\\ A \to 0A0\ |\ 0A1\ |\ \lambda\\ B \to 0B\ |\ 1B\ |\ \lambda
S \to A\ |\ B\\ A \to 0S0\ |\ 1S1\ |\ \lambda\\ B \to 0S1\ |\ 1S0\ |\ \lambda
S \to A\ |\ B\\ A \to 0A0\ |\ 1A1\ |\ \lambda\\ B \to 0B1\ |\ 1B0\ |\ \lambda
S \to aSa\ |\ bSb\ |\ X\\ X \to aXb\ |\ bXa\ |\ a\ |\ b\ |\ \lambda
S \to WXW'\\ X \to aX\ |\ bX\ |\ \lambda\\ W \to aW\ |\ bW\ |\ \lambda\\ W' \to W'a\ |\ W'b\ |\ \lambda