(→Resolução) |
|||
(4 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
+ | {{TOCright}} | ||
== Tópicos == | == Tópicos == | ||
Análise lexical: expressões regulares, algoritmo de Thompson (construção do NFA), determinização (construção do DFA), minimização de DFA, análise de entrada. | Análise lexical: expressões regulares, algoritmo de Thompson (construção do NFA), determinização (construção do DFA), minimização de DFA, análise de entrada. | ||
Line 5: | Line 6: | ||
== Exercício 1 == | == Exercício 1 == | ||
+ | |||
Para cada uma das expressões regulares seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é '''Σ = { a, b }'''. | Para cada uma das expressões regulares seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é '''Σ = { a, b }'''. | ||
− | * [[Theoretical Aspects of Lexical Analysis/Exercise 1| | + | * [[Theoretical Aspects of Lexical Analysis/Exercise 1|Problema 1]]: '''(a|b)*''' |
− | * [[Theoretical Aspects of Lexical Analysis/Exercise 2| | + | * [[Theoretical Aspects of Lexical Analysis/Exercise 2|Problema 2]]: '''(a*|b*)*''' |
− | * [[Theoretical Aspects of Lexical Analysis/Exercise 3| | + | * [[Theoretical Aspects of Lexical Analysis/Exercise 3|Problema 3]]: '''((ε|a)b)*''' |
− | * [[Theoretical Aspects of Lexical Analysis/Exercise 4| | + | * [[Theoretical Aspects of Lexical Analysis/Exercise 4|Problema 4]]: '''(a|b)*abb(a|b)*''' |
+ | |||
+ | == Exercício 2 == | ||
+ | Para cada uma das seguintes sequências ordenadas seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é Σ = { a, b }. Indicar em quantos passos é processada a entrada apresentada. | ||
+ | |||
+ | * [[Theoretical Aspects of Lexical Analysis/Exercise 5|Problema 1]]: '''G = { ab, ab*, a|b }''', input string = '''abaabb''' | ||
+ | * [[Theoretical Aspects of Lexical Analysis/Exercise 6|Problema 2]]: '''G = { aa, aaaa, a|b }''', input string = '''aaabaaaaa''' | ||
− | == | + | == Resoluções == |
As ligações acima contêm as soluções para os exercícios propostos. | As ligações acima contêm as soluções para os exercícios propostos. |
Contents |
Análise lexical: expressões regulares, algoritmo de Thompson (construção do NFA), determinização (construção do DFA), minimização de DFA, análise de entrada.
Analisadores lexicais (múltiplas expressões/tokens em simultâneo).
Para cada uma das expressões regulares seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é Σ = { a, b }.
Para cada uma das seguintes sequências ordenadas seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é Σ = { a, b }. Indicar em quantos passos é processada a entrada apresentada.
As ligações acima contêm as soluções para os exercícios propostos.
Procurar resolver sem consultar.