COSC 418/CPMA 584: Formal Languages and Automata Homework #3
Due: 10/4/18
Points: 80(100)
- Do Exercise 3.1.2 from the book.
- Show that the language {aibai | i ≥ 0 } is not a regular language.
- Show that the language {aibai | i ≥ 0 } is a context-free language.
- Write a grammar that accepts strings which have all delimiters properly paired and properly nested, and only those such strings. The pairs of delimiters are “<” and “>”, “(” and “)”, “{” and “}”, “[” and “]”. The strings are over the alphabet of delimiters plus the lowercase letters. For example, the grammar should accept the string “{a}[(dog)]” but not “{[}]xyz” and not “(“.
- Draw a PDA that accepts the language of the previous question.
- Minimize the following DFA. You may check your answer with JFLAP, but try it by hand first.
- Give an algorithm that checks if two regular expressions represent the same language.
- Is the sentence “Colorless green ideas sleep furiously” ambiguous given the grammar from Slide 7 of Unit 5? Prove or disprove your answer.
- (CPMA 584) Prove that L(M) is a subset of L(G) where M is a DFA and G is the grammar formed from M by the construction given on Slide 22 of Unit 5.
10.(CPMA 584) Do Exercise 3.2.1 from the book.
Last modified: Sept. 26, 2018
Dr. Donald L. Simon, simon@mathcs.duq.edu