Assignment 6.2 [15 points]

Do Chapter 5 Exercises (not Programming Problems!) 2 - 5, 6a, 6b, 6c, 9a, 10 - 12, 13a, 13b

You can submit your solutions to these problems as a Word doc, or, if you prefer to write out the solutions, you can take a picture and submit the picture.

EXERCISES 1. Trace the following recursive functions: a. isPal with the string abcdeba b. isAnBn with the string AABB c. endPre with the expression - abcd 2. Consider the language that the following grammar defines: = $S = abba bb Write all strings that are in this language and that contain seven or fewer characters. Write a recursive grammar for the language of strings of one or more letters. The first letter of each string must be uppercase, and all other letters in the string must be lowercase. 4. Consider a language of character strings that contain only dots and dashes. All strings in this language contain at least four characters and begin with either two dots or two dashes. If the first two characters are dots, the last one must be a dash; if the first two characters are dashes, the last one must be a dot. Write a recursive grammar for this language. Consider a language of strings that contains only X, Y's and Zs. A string in this language must begin with an X If a Y is present in a string, it must be the final character of the string. a. Write a recursive grammar for this language. b. Write all the possible two-character strings of this language. 6. Consider a language of words, where each word is a string of dots and dashes. The following grammar describes this language: = = = - a. Write all three-character strings that are in this language. b. Is the string in this language? Explain. c. Write a seven-character string that contains more dashes than dots and is in the language. Show how you know that your answer is correct. d. Write pseudocode for a recursive recognition function is in(str) that returns true if the string str is in this language and returns false otherwise. 7. Consider the following grammar: word> = R = OP = 1 Write pseudocode for a recursive function that returns true if a string is in this language and return false otherwise, Consider the following grammar: = empty string = WA a. Write pseudocode for a recursive function that returns true if a string is in this language and returns false otherwise b. Is the string & W#W in this language? 9. Let L be the language L = {S.S is of the form AB, for somen >0} Thus, a string is in Lif and only if it starts with a sequence of A's and is followed by a sequence of twice as many B's. For example, AABBBB is in L, but ABBB, ABBABB, and the empty string are not a. Give a grammar for the language L. b. Write a recursive function that determines whether the string strExp is in L. 10. Is +*-Wettde-e a prefix expression? Explain in terms of the grammar for prefix expressions 11. Is ableefg +d+a postfix expression? Explain in terms of the grammar for postfix expressions. 12. Consider the language that the following grammar defines: = = 48 = 12 a. Write all three-character strings that are in this language. b. Write one string in this language that contains more than three characters. 13. Consider a language of the following character strings: The letter A, the letter B, the letter followed by a string that is in the language, and the letter followed by a string in the language. For example, these strings are in this language: A, CA, CCA, DCA, B, CB, CCB, DB, and DCCB. a. Write a grammar for this language. b. Is CAB in this language? Explain c. Write a recursive recognition algorithm for this language. 14. Consider the language that the following grammar defines = Slaalbb- lyylzz Equivalently, L = {sSreverse(s):s is a string of letters of length 20 Note that this language is very similar to the language of palindromes, but there is a special middle character here. The algorithm that this chapter gave for recognizing palindromes can be adapted easily to this language. The algorithm, which is recursive and processes the string str from both ends toward the middle, is based on the following facts: A string with no characters is not in the language. A string with exactly one character is in the language if the character is a $. A longer string is in the language if the ends are identical letters and the inner substring(from the second character to the next-to-last character of str) is in the language. Describe a recursive recognition algorithm that processes the string from left to right, reading one character at a time without saving the string for future reference. Write a C++ function that implements your algorithm 15. Consider the following recursive function: int p(int x) if (x * = $S = abba bb Write all strings that are in this language and that contain seven or fewer characters. Write a recursive grammar for the language of strings of one or more letters. The first letter of each string must be uppercase, and all other letters in the string must be lowercase. 4. Consider a language of character strings that contain only dots and dashes. All strings in this language contain at least four characters and begin with either two dots or two dashes. If the first two characters are dots, the last one must be a dash; if the first two characters are dashes, the last one must be a dot. Write a recursive grammar for this language. Consider a language of strings that contains only X, Y's and Zs. A string in this language must begin with an X If a Y is present in a string, it must be the final character of the string. a. Write a recursive grammar for this language. b. Write all the possible two-character strings of this language. 6. Consider a language of words, where each word is a string of dots and dashes. The following grammar describes this language: = = = - a. Write all three-character strings that are in this language. b. Is the string in this language? Explain. c. Write a seven-character string that contains more dashes than dots and is in the language. Show how you know that your answer is correct. d. Write pseudocode for a recursive recognition function is in(str) that returns true if the string str is in this language and returns false otherwise. 7. Consider the following grammar: word> = R = OP = 1 Write pseudocode for a recursive function that returns true if a string is in this language and return false otherwise, Consider the following grammar: = empty string = WA a. Write pseudocode for a recursive function that returns true if a string is in this language and returns false otherwise b. Is the string & W#W in this language? 9. Let L be the language L = {S.S is of the form AB, for somen >0} Thus, a string is in Lif and only if it starts with a sequence of A's and is followed by a sequence of twice as many B's. For example, AABBBB is in L, but ABBB, ABBABB, and the empty string are not a. Give a grammar for the language L. b. Write a recursive function that determines whether the string strExp is in L. 10. Is +*-Wettde-e a prefix expression? Explain in terms of the grammar for prefix expressions 11. Is ableefg +d+a postfix expression? Explain in terms of the grammar for postfix expressions. 12. Consider the language that the following grammar defines: = = 48 = 12 a. Write all three-character strings that are in this language. b. Write one string in this language that contains more than three characters. 13. Consider a language of the following character strings: The letter A, the letter B, the letter followed by a string that is in the language, and the letter followed by a string in the language. For example, these strings are in this language: A, CA, CCA, DCA, B, CB, CCB, DB, and DCCB. a. Write a grammar for this language. b. Is CAB in this language? Explain c. Write a recursive recognition algorithm for this language. 14. Consider the language that the following grammar defines = Slaalbb- lyylzz Equivalently, L = {sSreverse(s):s is a string of letters of length 20 Note that this language is very similar to the language of palindromes, but there is a special middle character here. The algorithm that this chapter gave for recognizing palindromes can be adapted easily to this language. The algorithm, which is recursive and processes the string str from both ends toward the middle, is based on the following facts: A string with no characters is not in the language. A string with exactly one character is in the language if the character is a $. A longer string is in the language if the ends are identical letters and the inner substring(from the second character to the next-to-last character of str) is in the language. Describe a recursive recognition algorithm that processes the string from left to right, reading one character at a time without saving the string for future reference. Write a C++ function that implements your algorithm 15. Consider the following recursive function: int p(int x) if (x *