Problem 3. Consider the following scheme to describe chess positions. We use the letters P, B, N, R, Q, and K to denote, respectively, white pawns, bishops, knights, rooks, queens and kings; their black counterparts are denoted by the corresponding lower-case letter; empty board cells are denoted by the underscore character (); and a chess position is denoted by the string of characters that is obtained by traversing the board in row-major order. For instance, the position depicted below is denoted by the string ---r----__---_R_---------pkn ------P___BP-_-q_K___P_---------Q. a b c d e f g h Consider some standard rule set of chess and the language of all strings over the alphabet P,B, N, R,Q,K,P, b,n,r, q, k,} that, under our established scheme, represent a legal chess position from which, if White were to start the game activate and play perfectly, White would be assured victory. Is this language regular? Prove that your answer is correct. Problem 4. One way to define a balanced sequence of parentheses is as a string over the alphabet S={(,)} such that: its total number of characters equals its total number of characters; and in each of its prefixes, there are at least as many characters as there are ) characters. The debt of a prefix of a balanced sequence of parentheses is the number of (characters in the prefix minus the number of characters in it. The depth of a balanced sequence of parentheses is the maximum debt among all its prefixes. For a given deN, we can define the language Pd of all balanced sequences of parentheses having depth at most d. We can also define the language P=UPa = P U PU... DEN of all balanced sequences of parentheses. Later in the course we shall see that P is not a regular language. This will be shown in a systematic manner, but it is possible to prove this fact using only material covered in class. For now this is left as a challenging exercise but is not part of the assignment. In this problem you must answer the following question and prove that your answer is correct. Which values of de N are such that Pd is a regular language? Problem 3. Consider the following scheme to describe chess positions. We use the letters P, B, N, R, Q, and K to denote, respectively, white pawns, bishops, knights, rooks, queens and kings; their black counterparts are denoted by the corresponding lower-case letter; empty board cells are denoted by the underscore character (); and a chess position is denoted by the string of characters that is obtained by traversing the board in row-major order. For instance, the position depicted below is denoted by the string ---r----__---_R_---------pkn ------P___BP-_-q_K___P_---------Q. a b c d e f g h Consider some standard rule set of chess and the language of all strings over the alphabet P,B, N, R,Q,K,P, b,n,r, q, k,} that, under our established scheme, represent a legal chess position from which, if White were to start the game activate and play perfectly, White would be assured victory. Is this language regular? Prove that your answer is correct. Problem 4. One way to define a balanced sequence of parentheses is as a string over the alphabet S={(,)} such that: its total number of characters equals its total number of characters; and in each of its prefixes, there are at least as many characters as there are ) characters. The debt of a prefix of a balanced sequence of parentheses is the number of (characters in the prefix minus the number of characters in it. The depth of a balanced sequence of parentheses is the maximum debt among all its prefixes. For a given deN, we can define the language Pd of all balanced sequences of parentheses having depth at most d. We can also define the language P=UPa = P U PU... DEN of all balanced sequences of parentheses. Later in the course we shall see that P is not a regular language. This will be shown in a systematic manner, but it is possible to prove this fact using only material covered in class. For now this is left as a challenging exercise but is not part of the assignment. In this problem you must answer the following question and prove that your answer is correct. Which values of de N are such that Pd is a regular language