A language over a finite alphabet is said to be regular if there exists a finite automaton such that . Here
Answer the following questions:
(1) We fix an alphabet by . For the language below, present a nondeterministic finite automaton (NFA) such that: , and the number of states of is not greater than .
(2) Assume that is a finite alphabet. Prove the following: any finite language is regular. Here is a nonnegative integer.
(3) We fix an alphabet by . For the language in Question (1), present a deterministic finite automaton (DFA) such that: , and the number of states of is not greater than . Here denotes the complement of .
(4) Give a decision procedure for the following problem, and explain it briefly.
Input: Nondeterministic finite automaton .
Output: Whether the language is an infinite set or not.
Prove: if is finite alphabet, then any finite language is regular, .
That is we should construct a finite automaton accepting .
We can construct a -NFA containing "branches", each recognizing .
Now, for every -NFA, there must exist equivalent DFA recognizing the same language.
We can also construct the DFA explicitly.
Start with automaton (NFA) recognizing : there are states, the last one is accepting and transitions are labeled with next letters of .
For () try to traverse the automaton as far as you can, i.e. until transition for symbol exist.
If we can go no further, that is we read the longest common prefix of and some , , then we make a new branch from a current state.
This branch consist of states and transitions labeled .
Now we need to assure that we constructed a DFA.
For every state missing some transitions on some letters, add those transition leading to a "dead state", i.e. nonaccepting state with a self-loop labeled .
Given NFA , decide whether is empty or not.
% For every NFA , there exist equivalent DFA , that is, (subset construction).
% Let's examine such DFA .
Since language of is regular, then from pumping lemma we can "pump" words longer than some – pumping lemma constant.
That is, if has some word longer than , then is infinite.
We just need to check every possible word : .
If any such word is accepted by , then is infinite.
We don't need to check words longer of : if a word is longer than , then from PL, we can iterative reduce its length, so has length shorter than .
How to choose ? We know that for every NFA , there exist equivalent DFA , that is, (subset construction).
We don't need to construct such DFA.
All we know is that, might have exponentially more states than .
Take , where is set of 's states.