CMSC 330 Spring 2011 Practice Problems 2 1. For each regular expression r below, (i) say whether or not r✓ holds and (ii) give the transitions of r. a. r = a* b. r = (a|ab)*a c. r = a*(ba*ba*)* 2. For each regular expression in Question 1 i. Reduce the RE to an NFA using the algorithm described in class. ii. Reduce the resulting NFA to a DFA using the subset algorithm. iii. Show whether the DFA accepts / rejects the strings “aba”, “aa”, “bbabb”. 3. Context-Free Grammars a. List the 4 components of a context-free grammar. b. Describe the relationship between terminals, non-terminals, and productions. c. Define ambiguity. d. Describe the difference between scanning & parsing. 4. Describing Grammars a. Describe the language accepted by the following grammar: S → abS | a b. Describe the language accepted by the following grammar: S → aSb | ε c. Describe the language accepted by the following grammar: S → bSb | A A → aA | ε d. Describe the language accepted by the following grammar: S → AS | B A → aAc | Aa | ε B→ bBb | ε e. Describe the language accepted by the following grammar: S → S and S | S or S | (S) | true | false f. Which of the previous grammars are left recursive? g. Which of the previous grammars are right recursive? h. Which of the previous grammars are ambiguous? Provide proof. 5. Creating Grammars a. Write a grammar for axby, where x = y b. Write a grammar for axby, where x > y c. Write a grammar for axby, where x = 2y d. Write a grammar for axbyaz, where z = x+y e. Write a grammar for axbyaz, where z = x-y f. Write a grammar for all strings of a and b that are palindromes. g. Write a grammar for all strings of a and b that include the substring baa.h. Write a grammar for all strings of a and b with an odd number of a’s and an odd number of b’s. i. Write a grammar for the set of regular expressions over the alphabet {a, b}. j. Which of your grammars are ambiguous? Can you come up with an unambiguous grammar that accepts the same language? 6. Derivations, Parse Trees, Precedence and Associativity For the following grammar: S → S and S | true a. List 4 derivations for the string “true and true and true”. b. Label each derivation as left-most, right-most, or neither. c. List the parse tree for each derivation d. What is implied about the associativity of “and” for each parse tree? For the following grammar: S → S and S | S or S | true e. List all parse trees for the string “true and true or true” f. What is implied about the precedence/associativity of “and” and “or” for each parse tree? g. Rewrite the grammar so that “and” has higher precedence than “or” and is right
View Full Document
Unlocking...