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 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