P07-T3 Sétima aula prática (Turma 3)

29 outubro 2012, 11:00 • Francisco Miguel Alves Campos de Sousa Dionísio

Gramática livre de contexto certificado da adição. Conversão de gramáticas regulares em autómatos finitos determinísticos (dois exercícios) e determinação da expressão regular dado um autómato (dois exercícios).

Expressões regulares I

29 outubro 2012, 09:30 • José Félix Costa

Expressões regulares.

Linguagem denotada por uma expressão regular. Exemplos de expressões regulares.

Resolução (ou conversão) de autómatos em expressões regulares através de algoritmo.

P06-T2 Sexta aula prática (Turma 4)

29 outubro 2012, 08:00 • Francisco Miguel Alves Campos de Sousa Dionísio

Determinação de gramáticas regulares para linguagens dadas, de alfabeto {0,1} das palavras a) que começam em 11 e b) que começam com um número par de zeros seguido de um número ímpar de uns e que começam e acabam em 1.  Verificação de que as gramáticas geram determinadas palavras.  Em diversos casos a melhor motivação para a gramática proveio do autómato correspondente.Transformação da gramática regular num autómato equivalente.

Gramáticas livres de contexto. Gramáticas para as linguagens {a^nb^n, n>=0}, {a^nb^n:2, n>=0} e certificado para a função sucessor.

P06-T2 Sexta aula prática (Turma 2)

26 outubro 2012, 08:00 • Francisco Miguel Alves Campos de Sousa Dionísio

Determinação de gramáticas regulares para linguagens dadas, de alfabeto {0,1} das palavras a) que começam em 11 e b) que começam com um número par de zeros seguido de um número ímpar de uns e que começam e acabam em 1.  Verificação de que as gramáticas geram determinadas palavras.  Em diversos casos a melhor motivação para a gramática proveio do autómato correspondente.

Gramáticas livres de contexto. Gramáticas para as linguagens {a^nb^n, n>=0}, {a^nb^n:2, n>=0} e certificado para a função sucessor.

TURMA 106: Modelação de gramáticas I

25 outubro 2012, 09:30 • José Félix Costa

Exercícios de modelação de gramáticas. Conversão de gramáticas em autómatos.

Exercício: Indique uma gramática regular das palavras sobre {0,1} que (a) começam em '11', (b) terminam em '00', (c) começam em '0' ou (inclusivo) terminam em '1'.

Exercício: Indique uma gramática regular das palavras sobre {0,1} que (a) têm um número par de '0's e um número ímpar de '1's, (b) começam e terminam em '1', (c) tais que entre quaisquer dois '1's consecutivos existam exactamente dois '0's.

Exercício: Indique uma gramática regular das palavras sobre {0,1,2} tais que a soma de dois números consecutivos (interpretando as letras como números) seja inferior ou igual a 2.

TPC

Exercício: Indique uma gramática regular que gere a linguagem reconhecida pelo autómato de elementos Q={P,Q,R}, \Sigma={0,1}, estado inicial 'P', estados finais {Q,R} e função de transição dada por: \delta(P,0)=Q, \delta(P,1)=R, \delta(Q,0)=P, \delta(Q,1)=R, \delta(R,0)=Q, \delta(R,1)=Q.

Exercício: Considere a gramática regular de elementos V={S,A}, \Sigma={0,1}, símbolo inicial S e produções S > 0A | 1, A > 1A | \epsilon; determine um autómato finito determinístico que reconheça a linguagem gerada por esta gramática.

Exercício: Considere a gramática regular de elementos V={S,A}, \Sigma={0,1}, símbolo inicial S e produções S > 0A | 1B | \epsilon, A > 1C, C > 0A | \epsilon, B > 1B | \epsilon; determine um autómato finito determinístico que reconheça a linguagem gerada por esta gramática.

Exercício: Indique uma gramática regular que gere a linguagem reconhecida pelo autómato de elementos Q={A,B,C,D}, \Sigma={0,1}, estado inicial 'A', estados finais {D} e função de transição dada por: \delta(A,0)=A, \delta(A,1)=B, \delta(B,0)=C, \delta(B,1)=B, \delta(C,0)=A, \delta(C,1)=D, \delta(D,0)=C, \delta(D,1)=B.

Exercício: Indique uma gramática regular que gere a linguagem reconhecida pelo autómato de elementos Q={S,T,U,V}, \Sigma={0,1}, estado inicial 'S', estados finais {V} e função de transição dada por: \delta(S,0)=V, \delta(S,1)=T, \delta(T,0)=U, \delta(T,1)=V, \delta(U,1)=T.

Exercício: Considere a gramática regular de elementos V={S,A}, \Sigma={0,1}, símbolo inicial S e produções S > 0A, A > 0A | 1A | 1; determine um autómato finito não determinístico que reconheça a linguagem gerada por esta gramática.

Exercício: Seja L = {x0y: x,y in {0,1}*}; indique um autómato finito não determinístico que reconheça L; indique um autómato determinístico que reconheçe L; indique uma gramática regular que gere L; resolva a gramática para encontrar uma expressão regular que denote L.