Explain finite automata with an example.
A finite automaton is a mathematical model of computation that consists of a set of states, a set of input symbols, a transition function that maps states and input symbols to a next state, a start state, and a set of accept states.
Example: A finite automaton that accepts all strings with an even number of 0s. It would have two states: S0 (even number of 0s) and S1 (odd number of 0s). The start state would be S0. If the input is 0, the state changes. If the input is 1, the state remains the same. The accept state is S0.
What is the difference between regular languages and context-free languages?
Regular Languages: Can be recognized by finite automata. They are generated by regular grammars.
Context-Free Languages: Can be recognized by pushdown automata. They are generated by context-free grammars and can describe most programming language syntax.
Explain the concept of NP-completeness with an example problem.
NP-complete problems are a class of problems for which no efficient algorithm is known. They are the hardest problems in the NP (nondeterministic polynomial time) class. If a polynomial-time algorithm exists for any NP-complete problem, then a polynomial-time algorithm exists for all problems in NP.
Example: The Traveling Salesperson Problem (TSP)
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
How does the pumping lemma work?
The pumping lemma for regular languages is a theorem that states that for any regular language, any sufficiently long string in the language can be "pumped" – that is, have a middle section of the string repeated a number of times to produce a new string that is also in the language. It is often used to prove that a language is not regular.
Compare deterministic and non-deterministic automata.
Deterministic Finite Automata (DFA): For each state and input symbol, there is exactly one transition to a next state.
Non-deterministic Finite Automata (NFA): For each state and input symbol, there can be zero, one, or more transitions to a next state. An NFA accepts a string if there is at least one path from the start state to an accept state.
Explain Turing machines. Why are they important?
A Turing machine is a mathematical model of computation that defines an abstract machine which manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.
They are important because they provide a theoretical foundation for the limits of computation.
How does decidability differ from undecidability?
Decidability: A problem is said to be decidable if there exists an algorithm that can determine whether a given input string is in the language or not. The algorithm must halt on all inputs.
Undecidability: A problem is undecidable if no such algorithm exists. The most famous example of an undecidable problem is the Halting Problem.