COT3100 Summer 2001 Recitation on Languages and Machines 07 19 2001 1 Let A B and C be sets of strings Prove or disprove that A B C A B A C Only one subset relation can be proved namely we can prove that A B A C A B C It actually means that A B A C is smaller then A B C because there might be a string that belongs to both A B and A C although it can not be represented as some prefix from A and a suffix that belong to both B and C So here is a counterexample that disproves A B C A B A C A a ab B b C B C b A B C ab abb A B ab abb A C a ab and A B A C abb So ab A B C but ab A B A C so it s not the case that always A B C A B A C 2 Let A B and C be sets of strings Prove or disprove that if A B then A B Assume A B To prove A B take some string w A to show that w B By definition of Kleene A A0 A1 A2 w A means that w An where n is some integer n 0 w An implies that w u1u2 un where ui A for i 1 2 n Since A B ui A implies that ui B and then w u1u2 un Bn By Kleene star definition Bn B so that w Bn implies w B 3 Consider two languages represented by regular expressions L1 abc and L2 ab c Prove or disprove that L1 L2 We can disprove that L1 L2 if we find a string which belongs to one of languages and does not belong to the other Strings in L1 consist in some number of repetition pf the pattern abc i e some number of substrings starting with ab and followed by some number of c s this number may be 0 In other words any sequence of c s must be preceded by ab For example ababccabccccabc L1 Strings in L2 consist from any number of substrings ab and c in any order In particular they may start with some number of c s i e cc L2 but cc L1 4 Consider the following DFA a b b b 0 1 2 a a 3 1 a b a Give a sequence of configurations of the DFA for the input string w aabbbba q0 aabbbba q0 abbbba q0 bbbba q1 bbba q2 bba q2 ba q2 a q3 b Is w accepted by the DFA No because q3 is not an accepting state c Give a regular expression of strings accepted by the DFA a bbb 5 Construct a DFA to recognize the language represented by the regular expression a b abb over the alphabet a b Give the diagram and transition table b a a 0 b 1 2 b 3 a a b q0 q1 q2 q3 a q1 q1 q1 q1 b q0 q2 q3 q0 2
View Full Document
Unlocking...