In the following, we represent a deterministic finite automaton as a quintuple (where is a finite set of states, is a finite set of input symbols, is the transition function, is the initial state, and is the set of final states), and a context-free grammar as a quadruple (where is a finite set of non-terminal symbols, is a finite set of terminal symbols, is a finite set of production rules, and is the start symbol).
A context-free grammar is in Chomsky normal form if each production rule is of the form:
,
, or
,
where is a non-terminal symbol, and are non-terminal symbols other than , is a terminal symbol, and is an empty sequence. We write for the language accepted by a deterministic finite automaton , and for the language generated by a context-free grammar .
Answer the following questions:
(1) Let be a deterministic finite automaton. Give a deterministic finite automaton that accepts the complement of , i.e., . Here, you may assume that is a total function.
(2) Describe an algorithm that takes a context-free grammar as an input, and decides whether .
(3) Given a context-free grammar in Chomsky normal form and a deterministic finite automaton , we define a context-free grammar as follows:
Here, assume . Prove that holds.
(4) Give a method to decide, given a context-free grammar in Chomsky normal form and a deterministic finite automaton as inputs, whether or not holds. You may use the results of questions (1), (2), and (3).
We call symbol \emph{generating} if for some string of terminals.
If there's no such string, then is \emph{nongenerating}.
Language of grammar is empty iff start symbol is nongenerating.
We can find set of generating symbols using the algorithm below.
Symbols that are not marked generating, are nongenerating.
The algorithm:
Base. Every terminal symbol form is generating.
Induction. If for some production , is known to be generating, then is .