Ch 1 : Regular Languages Flashcards
Why is a language considered non-regular? What does this mean?
Regular languages don’t need memory, and thus can be represented by a FSM/FA. Non-regular languages need memory in order to recognize potentially infinite input.
How does the pumping lemma play into regular vs. non-regular languages?
Regular languages have a special property.
If we can show that a language does not have this property, then it is not regular.
The property that they have is that regular languages are able to be pumped if they are a minimum length.
IOW, each string has a section that is repeated at least once and still remain part of the language.
What is the main principle behind the pumping lemma and why does it work?
[INSERT]
The pigeonhole principle.
How do we us the pumping lemma to prove that a language B is not regular?
- Assume B is regular to get a contradiction
- Use PL to guarantee existence of a string of length at least p that can be pumped
- Find a string s in B at least as long as p that cannot be pumped.
- Demo that s cannot be pumped by considering every possible way of dividing s into x, y, z and for each, find a value of i that make xy^iz not an element of B
(involves grouping into several cases and analyzing individually)
( May need to ‘hunt’ for s…try to find ‘essence’ of b’s irregularity)
What is the pumping lemma?
If A is a regular language….
Then there is a number p,
where s (any string in A of length at least p)
may be divided into three pieces with….
- for EVERY i >= 0, xy^iz E A
…….its in the language, for every number of pumps - |y| > 0
…..the cycle has at least one edge in it - |xy|
What is the difference between the terms accept recognize, decide
[INSERT]
What is a GNFA, as compared to an NFA?
NFA where transition arrows can have any reg expression, not just members of the alphabet or. Epsilon
What are the three special conditions of a GNFA?
Start state goes to every other state but no arrows in
End state has arrows in from every state but none going out
Other states have arrows to every other state including their own.
What is the definition of epsilon closure?
E(R) for any state R of M is the collection of states that can be reached from members of R by going only along epsilon arrows, including members of R themselves.
