Non-deterministic finite automata

26 setembro 2013, 12:30 • José Félix Costa

[[

Decidability of some sets involving binary matrices. (Homework: The set of matrices 2 x n read by columns such that the lower line is the triple of the upper line.)

Pumping lemma applied to some sets involving arithmetical predicates.

]]

 

Non-deterministic finite automata. Conversion of non-deterministic automata into deterministic automata.

 

Pumping lemma

20 setembro 2013, 10:30 • José Félix Costa

Proof of the pumping lemma.

Resolution of some exercises: see summary of the previous lecture.

Introduction to non-deterministic finite automata.

 

Automata

19 setembro 2013, 12:30 • José Félix Costa

Automata in the context of the sciences in general and complexity theory in particular.

Finite automata, regular languages.

Pumping lemma: statement and application.

Seminal paper in automata theory: McCullock and Pitts paper.

 

Exercises:

 

Specify an automaton:

Especifique um autómato finito determinístico que, de entre as palavras que se escrevem com os símbolos 0 e 1, aceite apenas as que terminam em 1.

Especifique um autómato finito determinístico que, de entre as palavras que se escrevem com os símbolos 0 e 1, aceite apenas aquelas que terminam em 1 seguido de um número par de zeros.

Especifique um autómato finito determinístico que, de entre as palavras que se escrevem com os dígitos 0, 1 e 2, aceite apenas aquelas cuja soma dos dígitos seja divisível por 3.

Especifique um autómato finito que, de entre as palavras que se escrevem com os símbolos 0 e 1, aceite apenas as que têm um '1' na penúltima posição.

Especifique um autómato finito que, de entre as palavras que se escrevem com os símbolos 0 e 1, aceite apenas as que têm um '1' na antepenúltima posição.

Especifique um autómato finito que, de entre as palavras que se escrevem com os símbolos 0 e 1, aceite apenas as que têm um '1' na última ou (inclusivo) na penúltima posição.

Especifique um autómato finito que, de entre as palavras que se escrevem com o símbolo 0, aceite apenas as que têm tamanho par ou múltiplo de três.

Especifique um autómato finito determinístico que, de entre as palavras que se escrevem com letras do alfabeto {a,b}, aceite apenas as que entre dois 'a's consecutivos ocorre no máximo um 'b'.

Especifique um autómato finito determinístico que, de entre as palavras que se escrevem com letras do alfabeto {a,b}, aceite apenas as que começam e acabam na mesma letra.

Especifique um autómato finito determinístico que, de entre as palavras que se escrevem com letras do alfabeto {x,y,z}, aceite apenas as que terminam em 'yz'.

Especifique um autómato finito determinístico que, de entre as palavras que se escrevem com letras do alfabeto {0,1}, aceite apenas as que são formadas por um número par de '0's seguidos de um número ímpar de '1's.

Especifique um autómato finito determinístico que, de entre as palavras que se escrevem com letras do alfabeto {a,b}, aceite apenas as que contêm dois 'a's consecutivos ou dois 'b's consecutivos.´

 

Pumping Lemma

Mostre que a linguagem L = {0^n 1^n: n in N} (= {\epsilon, 01, 0011, 000111, 00001111, ...}) não é regular.

Mostre que a linguagem L = {w in {0,1}*: em w há igual número de 0's e de 1's} não é regular.

Mostre que a linguagem L = {w in {0,1}*: w é palíndromo e |w| é par} não é regular.

Mostre que a linguagem L = {ww: w é palavra binária} não é regular.

Mostre que a linguagem L = {0^m 1^n: m > n} não é regular.

Mostre que a linguagem L = {w in {0,1}*: w é palíndromo} não é regular.

Mostre que a linguagem L = {1^n^2: n in N} = {1, 1111, 111111111, 1111111111111111, ...} não é regular.

Mostre que a linguagem L = {w in {0,1}*: w não é palíndromo} não é regular.