跳到主要内容

東京大学 情報理工学系研究科 コンピュータ科学専攻 2018年8月実施 専門科目I 問題3

Author

kainoj

Description

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).

Kai

(1)

Given DFA , give an automaton accepting complement of , i.e. .

Let Now, iff ) which is occurs only when

(2)

Given CFG , decide wheaterh .

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 .

(3)

Looks pretty obvious from the construction. A nice induction'd make it.

(4)

If , then We can compute complement based on (Q1), intersection based on (Q3) and check for emptiness based on (Q2).