Aula Teórica 11

3 novembro 2011, 12:00 • Maria Paula Antunes Abrantes Gouveia

Revisão de alguns conceitos relativos a autómatos de pilha. Exemplos: autómatos de pilha para as seguintes linguagens (i) {1^n01^n: n ínteiro não negativo}; (ii) {wbw^R: w\in\{a,c}^*}; (iii) {wcw^R: w\in\{a,c}^*}}; (iiv) {ww^R: w\in\{a,c}^*}; (v) {1^n01^k01^{n+k}: n,k inteiros não negativos}. Linguagens livres de contexto. Proposição (só enunciado): Para cada gramática livre de contexto G existe um autómato de pilha M tal que L_M=L_G, e vice-versa. Referência ao lema da bombagem para linguagens livres de contexto. Exemplos de linguagens que não são livres de contexto.