Fundamentals of Computation Flashcards
(48 cards)
1
Q
What does DFA stand for and what is it?
A
- Deterministic Finite-state Automaton
- Machine with a set of states where each input symbol leads to exactly one next state
2
Q
What are the types of states in a DFA?
A
- Start state: Where the string begins
- Accepting state: If a string ends here, it is accepted
- Dump state: Dead-end state where invalid strings go, and it cannot be exited
- Unreachable state: A state that can’t be reached by any input string
3
Q
Can a DFA have unreachable accepting states?
A
No, all accepting states in a DFA must be reachable by some string
4
Q
What does NFA stand for and what is it?
A
- Non-deterministic Finite-state automaton
- An input symbol can lead to multiple possible next states
5
Q
What is the key difference between a DFA and an NFA?
A
- DFA uses a transition function (one symbol=one next state) whereas NFA uses a transition relation (one symbol=zero or more possible next states)
- NFAs don’t require dump states
6
Q
Do DFAs and NFAs need accepting states?
A
No but if they dont have any accepting states, they won’t accept any input strings
7
Q
Do DFAs and NFAs need transitions?
A
No, if they don’t have transitions, they can still accept the empty string
8
Q
What is algorithm A used for?
A
Converts an NFA to an equivalent DFA, using the idea of state subsets
9
Q
What are the steps of Algorithm A?
A
- Make new DFA states, using subset of NFA states (all possible combinations including the empty set)
- Mark a subset as accepting if any NFA state in it is accepting
- Add transitions based on NFA’s transitions
- Remove unreachable or isolated states
10
Q
Does every DFA have a corresponding NFA?
A
- Yes, every DFA can be seen as an NFA
- Not every NFA has a DFA
11
Q
What are epsilon transitions?
A
Epsilon transitions allow us to move to another state without having to consume a character
12
Q
How are epsilon transitions used for concatenation?
A
- Add epsilon transitions from accepting states in first NFA to start state in second NFA
- Make them not accepting
13
Q
How are epsilon transitions used for alternative/ or function?
A
- Add epsilon transitions from new start state to both starting states
14
Q
How are epsilon transitions used for star operators?
A
- Introduce new start state and make it accepting
- Add epsilon transition to existing start state
- Then add epsilon transitions from any accepting state to the origional starting state
15
Q
What is algorithm 4 used for?
A
To remove epsilon transitions
16
Q
How is algorithm 4 done?
A
- If you can reach an accepting state using only e-transitions, make it an accepting state, and copy all non-e transitions as normal
- Take each transition labelled x and add a transition from i to j labelled x if we can go between them using e-transitions followed by origional x
17
Q
If L1 is a subset of L2 then…
A
The intersect between L1 and the complement of L2 are empty
18
Q
Q to P is a simulation between automata A and B if:
A
- The start states are related
- If there is a transition x from q-a then then is also a transition x from p-b
- If q is an accepting state, then p must also be an accepting state
19
Q
Describe a minimum automaton M
A
- M is equivalent to a deterministic automaton A
- For every automaton B that is equivalent to A, the number of states in B will be >= to the number of states in M
20
Q
What makes 2 automata equivalent?
A
- If they accept the same language
- If they result in the same minimisation (disregarding state labels)
21
Q
Describe regular vs non-regular languages
A
- A language is regular is we can find a regex, DFA, NFA or NFA with e-transitions
- Non-regular languages cannot be finite
22
Q
What is the pigeonhole principle?
A
- For any word longer than n, there is a state that must be visited twice
- Used to prove languages are not regular
- As some part of the word can be pumped/repeated and still belong to the language (pumping lemma)
23
Q
What is a context-free grammar?
A
- Define languages using production rules
- Allow generation of non-regular languages
24
Q
What are the 4 things that CFGs consist of?
A
- Terminals: actual symbols
- Non-terminals: symbols that expand into other symbols
- Production rules: define transformations of non-terminals
- Start symbol: root of derivations
25
Explain grammar ambiguity
- A grammar is ambiguous if a string has **multiple valid parse trees** or derivations
26
What is a linear grammar?
- Have at most one non-terminal on the right side
- Always **unambiguous**
27
What programming structures are included in context-free grammars?
- Recursion
- Nested expressions
28
What three functions are context-free languages closed under and what does that mean?
- Concatenation
- Kleene star
- Union
- Means that when the function is applied it produces a CFL
29
What two functions are context-free languages **not** closed under and what does that mean?
- Intersection
- Complement
- Means their overlap may not be context-free
30
What are the three types of complexity?
- **Best case**: Fastest scenario
- **Average case**: Expected runtime over all inputs
- **Worst case**: Maximum time the algorithm takes
31
Explain big-O and give the notation
- Upper Bound
- The algorithm won't grow faster than this
- O(f(n))
32
Explain big-Omega and give the notation
- Lower bound
- The algorithm grows at least this fast
- Ω(f(n))
33
Explain big-Theta and give the notation
- Tight bound
- The algorithm grows exactly this fast (asymptotically)
- Θ(f(n))
34
Explain how we find the time complexities of loops
- Set no. of iterations = O(1)
- Variable no. of iterations = O(n)
- Nested variable loops = O(n^2)
35
How do we prove a set is uncountable?
- Produce an injection where the result differs from every number in the list by at least 1 digit
- Therefore cannot contain all real numbers
- This is the diagonal arguemnt
36
What does it mean for a set to be countably infinite and uncountable?
- If there exists a **bijection** between the set and N
- Has the **same size** as N
- Can be **listed** in sequence
- A set is uncountable if its larger than N and cannot be listed in a sequence
37
What is pair encoding and what is the formula
- Technicque used to represent two natural numbers as a single number
38
What is a loop variant and loop invariant?
- **Invariant**: If it is true at the start of the program, it is true while it executes and after it ends
- **Variant**: Approaches 0 in a loop
39
What is decidability and semi-decidability?
- Whether or not there is an algorithm that can answer yes or no for every input
- Algorithm always halts
- Semi-decidable is when the algorithm only needs to answer yes or no when the function is true
40
What is computability?
- Function is computable if there is a while program that, for every valid input, **eventually terminates** and produces the **correct output**
41
42
Explain whether or not the rewrite function => is deterministic and why?
- It is deterministic
- Determined by the structure of the current statement
43
How do you do pair encoding?
- n in binary
- then 0
- then m number of 1s
44
Why is proving partial correctness not decidable?
- To prove partial correctness of loops, we need to find a loop invariant
- Finding a sufficient one is undecidable
45
Why is the halting problem only partially decidable?
- We can detect when a program halts, but we cannot always detect non-termination
46
Are while and java equally expressive?
- Yes
- Both compute same set of functions
- **Church-turing thesis**- any function that can be computed by one turing-complete language can be computed by another
47
Why is the set of functions from while programs to while programs uncountable?
- Set of while programs in countable
- No. of possible functions mapping one to another is uncountable as there are **many more ways to define functions than programs**
48
What is the encoding function?
- Bijective function that takes a while program and returns its index
