跳到主要内容

東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年2月実施 問題3

Author​

kainoj

Description​

Let be a finite alphabet (i.e., a finite set of letters). We say that a word is a subsequence of a word if for some and . For example, is a subsequence of (let and ). We write if is a subsequence of . Answer the following questions.

(1) Give a non-deterministic finite automaton with at most states that accepts the language:

(2) Suppost that is the language accepted by a deterministic finite automaton (where is a finite set of states, is the transition function, is the initial state, and is the set of final states). Give a non-deterministic finite automaton that accepts the language:

(3) Supposet that is the language accepted by a deterministic finite automaton . Assume that the transition function is a total function. Give a deterministic finite automaton that accepts the language:

(4) Prove the correctness of your answer for question (3) above.

Kai​

(1)​

--> o --a--> o --a--> o --b--> (o)
   / \      / \      / \       / \
   \ /      \ /      \ /       \ /
    E        E        E         E

(2)​

Write

where indicates that is subsequence of . In other words, to in order to get a word from , we first fix a word and then intertwine its letters with some "garbage" from .

Let's fix . Let be sequence of states that visits when reading . Label transitions between 's with next letters of . Moreover, for each , add a loop to itself labeled with . Make the start state.

(3)​

First,

is kinda quirky. We already supposed that , so why do we need above?

Let's start with constructing a NFA which accepts . Let be a copy of , where we additionally put -labeled loops on every state. Intuitively, while traversing , in every state, we can have a "detour", i.e. accept some garbage.

Having constructed NFA , move to constructing equivalent DFA . It is feasible, and subset construction tells us how to it. Formally, define automaton accepting as . NFA such that is defined as:

where

is a "loop" on every state. Now, equivalent DFA is obtained by subset construction:

(4)​

Since every DFA has equivalent NFA and vice versa, I'll prove (Q3) for NFA .

Two steps:

  • .Since , then there must exits such that . is accepted both in and , since has exactly the same states as .Then, must be accepted by by following the loops on letters of which do not contribute to .
  • . To get such that , simulate on , skip the loops. Obviously , because states of and are the same and and will end up in the same final state of .