4 Flashcards
What is the Halting Problem?
Can you write an automated program that would answer this question without running the code: “Will the given program terminate or run forever?”?
Computers are…
messy
What is an automaton (automata)
Is a mathematical model of computing device.
Why do we build models?
Because we need mathematical simplicity & intellectual robustness.
A Finite Automata is…
a machine with limited amount of storage
Name two types of Finite Automata:
Deterministic Finite Automata (DFA)
Non-deterministic Finite Automata (NFA)
What are Strings?
Sequence of any symbols
What’s an alphabet?
Is a finite set of symbols called characters
What are Languages?
Sets of strings
Define Finite Automata
Is a simple type of mathematical machine for determining wether a string is contained within some language.
A finite automata consists of…
a set of states connected by transitions.
What’s characteristic of a DFA?
For each state in the DFA, there must be exactly one transition defined for each symbol in Σ
When do we have a Regular Language?
If L is a language and L(D)=L, we say that D recognises the language.
What is the complement of a Language?
Language of all strings in Σ* that aren’t in L.
Regular language are closed under complementation. What does this mean?
If L is a regular language, then L’ is also a regular language.
