Models - Automata and Regular Languages Flashcards
Define a formal language. What do ∑ and ∑ * have to do with this?
Define a deterministic finite automaton
Define the language of an automation
Define a regular language
How is a Nondeterministic finite automaton different from a DFA?
Define a Nondeterministic finite automaton
Define the language of a nondeterministic finite automaton
What can you say about the language of a DFA vs. the language of a NFA?
What is the pumping lemma for regular languages?
What is the intuition behind why the pumping lemma for regular languages is true?
L is regular so it has an automation A. We’ll take a word w that is longer than the number of states in A. -> a state in A must repeat itself in the run of A on the w (pigeon whole). -> the chain of letters between the repeating states could be erased or multiplied - and A will still conclude in an accepting state.
What can the pumping lemma be used to prove? How is this done?
The addition of a tail of any characters will either put both words into the language or exclude them both. That is, the tail works the same way on both words.
What is the Myhill–Nerode theorem?
How can you prove that an automation is minimal?
We have seen in class that the class REG (regular languages) is closed under what operations?
REG is closed under:
- Union
- Intersect
- Complement
- Concatenation
- Kleen star.
- XOR (proved in test)
What seems to you to be the easiest way to prove on a test that a language is in REG?
If possible, use closure properties of REG if it seems like the alternative is drawing a complex automata.
What are examples of non-regular languages?
How would you prove that a language is not regular?
Show that there are an infinite number of MN equivalence classes. (How?)
Prove the minimality of the DFA in the picture.