Chapter 2. Finite Automata Exercises DS020 오토마타형식언어 Chapter 2. Finite Automata Exercises September 18, 2003

1. For , construct DFA's that accept the sets consisting of all strings with exactly one a, all strings with at least one a, all strings with no more than three a's, all strings with at least one a and exactly two b's all strings with exactly two a's and at least three b's September 18, 2003

Solution 1. September 18, 2003

2. Find DFA's for the following languages on .   힌트 : 하나의 문자에 관하여 mod n 에 관한 문제가 나오면 state 수를 n개 만큼 두는 것이 편리합니다. 그럼 두 개의 문자가 나올 때는? September 18, 2003

Solution 2. September 18, 2003

3. Show that the language is regular. September 18, 2003

4. Show that the language is regular. September 18, 2003

5. Let L be the language . Show that L* is regular. 힌트 : Regular language의 조건이 무언인지 생각해 봅시다. September 18, 2003

6. Find a DFA that accepts the language defined by the NFA in follow figure. 힌트 : 윗길은 세 개의 a를 받고 아랫길은 짝수개의 a를 받는군요 September 18, 2003

Solution 6. September 18, 2003

7. Which of the strings 00, 01001, 10010, 000, 0000 are accepted by the following NFA? 힌트 : 직접 한번씩 해보도록 합시다. September 18, 2003

Solution 7. 00 : X 01001 : O 10010 : X 000 : O 0000 : X September 18, 2003

8. What is the complement of the language accepted by the NFA in follow figure? 힌트 : 먼저 그림이 accept하는 NFA를 찾아야 하겠죠? September 18, 2003

Solution 8. 그림에서 accept 하는 L은 aa* 따라서 여집합은 U-aa* =  September 18, 2003

9. Let L be the language accepted by the NFA in following figure 9. Let L be the language accepted by the NFA in following figure. Find an NFA that accepts . September 18, 2003

10. Find an NFA that accepts {a} 10. Find an NFA that accepts {a}* and is such that if in its transition graph a single edge is removed (without any other changes), the resulting automaton accepts {a}. 힌트 : 하나의 a만 accept하는 path와 모든 상황을 accept하는 path의 두 가지 path를 만들고, 하나를 지우면 되겠군요. 다른 방법도 있는지 찾아봅시다. September 18, 2003

Solution 10. 주어진 transition graph에서 아래쪽 edge를 제거하면 된다. September 18, 2003

11. Use the construction of Theorem 2 11. Use the construction of Theorem 2.2 to convert the NFA in following figure to a DFA. Can you see a simpler answer more directly? Theorem 2.2 : 결국 DFA와 NFA는 동치라는 내용입니다. September 18, 2003

Solution 11. September 18, 2003

12. Is it true that for any NFA the complement of L(M) is equal to the set ? If so, prove it. If not, give a counterexample. September 18, 2003

13. Give a simple verbal description of the language accepted by the DFA in the follow figure. Use this to find another DFA, equivalent to the given one, but with fewer states. September 18, 2003

14. Find minimal DFA's for the following languages. September 18, 2003

15. Minimize the states in the DFA depicted in the following diagram. 힌트 : mark and reduce 기법을 구사해봅시다. September 18, 2003

Solution 15. 도달하지 않는 상태 : q2, q4 구분 가능 : (q0, q3), (q0, q5), (q1, q3), (q1, q5) 구분 불가능 : (q0, q1), (q3, q5) September 18, 2003

16. Create Finite Automata for each of the following languages. The language of all strings that contain both an ’a’ and a ’b’ The language of strings that contain the substring ’aa’ and end in ’b’ The language of strings that contain the contain an ’a’ and don’t end in ’ba’ The language of strings that contain at least 2 ’a’s or at least 3 ’b’s The language consisting of (ab)* concatenated with (bb)* The language of strings where every block of ’a’s has an even number of ’a’s, except for the last block which has an odd number of ’a’s The language of binary numbers that are divisible by 5 (hint). 힌트 : 5로 나누었을 때 나머지는 몇 가지가 될까요? September 18, 2003

Solution 16. 7번 September 18, 2003

17. Each of the following statements is either True or False. It is possible for a FA to recognize an infinite language Every DFA is also a NFA For every NFA, there is an equivalent NFA that has no lambda transitions For every NFA, there is an equivalent NFA that has a single accept state If you swap the accept states and the reject states on any FA, the new machine will recognize the compliment of the original language The class of languages recognized by NFA is closed under complementation September 18, 2003