2. For each language below, decide whether it is regular or not, giving a reason
ID: 3589730 • Letter: 2
Question
2. For each language below, decide whether it is regular or not, giving a reason for your a) (ryz e 0,1* is a nonempty palindrome (A palindrome is a string that b) aPb: p and p2 are prime ]. (It is not known whether there are infinitely c) The set of all mathematically possible baseball scores. (If the visitors score m runs choice. reads the same forwards and backwards.) many such "twin primes." Give the answer for each case.) and the home team n runs, the score is reported as m -n. Ties are impossible.)Explanation / Answer
(a) It says that y has to be a nonempty palindrom, but it doesn't give any conditions for x and y. Therefore, everything except "epsilon" will be accepted. For example string "0" will be accepted with x=epsilon, y=0, z=epsilon. string "01" will be accepted with either x=epsilon, y=0, z=1 or x=0, y=1, z=epsilon. And so on. So basically language becomes (0+1)+. Therefore, the language is regular.
(b) There are two cases to consider here: 1. If there exist only a finite number of such twin primes. In that case, whatever large be the number of strings, but it will be finite. If any language has finite number of strings, the language is regular. Number can be any large, but if it's finite, the language is regular. Thus, in this case, the given language will be regular.
2. If there exist infinite number of such twin primes. In that case, we will need a counter or a stack to keep track of number of a's and number of b's. Also, we will need some logic to determine whether a number is prime or not. Finite Automata is not capable of providing these functionalities. Therefore, in this case, the language would not be regular. It will be CSL (Context Sensitive).
(c) The maximum possible score in a 9 innings baseball game is 114. So set of possible scores will be a finite set. And any language having finite number of members is regular. Thus, the given language is regular.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.