Please Attach This Question Paper on Top of Your Answer Sheets
Type Your Name Here:
CSE 5210Formal Languages and Automata TheorySpring 2010Exam 1
Points 50Time 70 min
(1a) Give a DFA for the set of all strings of a’s and b’s that must start with a b and may end with an a. Strings in the language include b, bba, bbb, baaaaba, etc. [5]
Second part is bogus. Just make sure the first character is b, then loop for a/b in final state.
(1b) Prove by induction that your machine accepts and rejects correctly.[5]
Now we are talking! Base case, string a (must reject), and string b (must accept). Extend accepted and rejected string of length n, by character a and b, four cases.
(2) Give a context-free grammar for the set of all strings of 0’s and 1’s of the form 0i1kwhere i>k.
Push more 0’s in the middle: S->0S1 | 0P, P-> 0P| e; note k could be zero.
(3) Give a regular expression for the set of all strings of 0’s and 1’s that contain at least one occurrence ofthe substring 00, AND at least one occurrence of the substring 11. For example, strings in the languageinclude 101001011001, 1100, 00111, etc. Very briefly justify your answer. [You may not first draw an automaton and translate it to a corresponding re.]
This does not ensure both 00 and 11 will be there: (0+1)*(00+11)(0+1)*
This enforces ordering, 00 before 11: (0+1)*00(0+1)*11(0+1)*
I will do this: (0+1)*00(0+1)*11(0+1)* + (0+1)*11(0+1)*00(0+1)*
(4a) Is the language described in question (1) regular (yes or no)? (4b) Is the language described in question (2) regular(yes or no)? (4c) Is the language described in question (3) regular (yes or no)? Write a simple explanation, or an appropriate proof, for each one, as the case may need.
1: yes, you are drawing a DFA
2: no, remembering how many (i) 0’s have been read is not possible by arbitrary DFA. However, pumping lemma is difficult to apply here, as pumping over 0’s will not violet the language property. You have to go reverse gear. For |DFA|=N accepting the language, pick up a string 0N1N-1 , and shrink over 0 to a string 0M1N-1, for M<N, which has to be accepted by the same DFA, where the string is illegal a la the language. This proof is required in your answer.
3. yes, a re is a rl.
(5a) The pumping lemma for regular languages dictates that any string of sufficient length from aregular language can be broken up into several parts. Briefly explain where those parts come from. In otherwords, brieflyoutline the part of the proof of the pumping lemma that shows how to break the string intosubstrings and the reason behind doing so. [7]
A pretty picture of how exhausted number of states in transition for the string demands the existence of a loop.
(5b) Suppose we wanted to define a new type of PDA that had two stacks instead of just one. Provide a formal definition for such a machine. Do not worry what this machine is for - you just need to show your capability to write a complete formal definition. [3]
Just define the eighth element for second stack in the tuple, and for the rest you may pipe dream – elements for second stack, transition functions, etc.