Question: Given a language L, consider the following 2-player game: player 1 picks a positive integerp player 2 picks a string s in L of length

Given a language L, consider the following 2-player game: player 1 picks a positive integerp player 2 picks a string s in L of length at least p Player 1 picks strings x, y, and z with s= xyz,|xy| sp, and ly[>0, Player 2 picks i EN Player 2 wins if xyiz L. Otherwise, Player 1 wins. The pumping lemma can be interpreted to say that Player 2 will have a winning strategy for this game if and only if Lis not regular. For the questions below, if the language is regular, write eithera regular expression or a deterministic FSM for it. If it is not regular, give a winning strategy for Player 2 in the "pumping lemma game". 5. Let L be the language of all strings of a's and b's of the form a'b* {j, k R} 6. Let L be the language of all strings of a's and b's of the form ab* {j, k Randj>k} 7. Let L be the language of all strings of a's and b's that have at least 2 a's and an odd #of b's 8. Let L be the language of all strings of a's and b's where abba occurs at least twice 9. Let L be the language of all strings of a's and b's that form a palindrome 10. Let L be the language of all strings of a's and b's that have a prime number of a's
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
