Question

For each of the following problems, decide whether the set A is regular. If the set is regular, give a FSM that recognizes it; if the set is not regular, prove it using the pumping lemma. 1. A={s11s | s∈{0}∗} Thus the strings 00011000 and 000001100000 are elements of A, but 00100 and 001100000 are not. 2. A={r11s | r,s∈{0}∗} Thus the strings 001100 and 0110000 are elements of A, but 00111100 and 000010 are not. 3. A={w∈{a,b}∗ | w contains at least two a’s and at most two b’s. 4. A={w∈{a,b}∗ | w contains exactly two more a’s than b’s. 5. A={30n1n2n4 | n>1} Thus 30011224 and 30001112224 are elements of A but 301124, 3001122, 0001112224, and 301224 are not. 6. A={30p1q2r4 | p≥1, q≥1, r≥1} Thus 30124 and 300122224 are elements of A but 30120124, 301122, and 3010124 are not. 7. A={w ∈ {0,1}∗ | there are 3 times as many 0’s as 1’s. 8. A={w ∈ {0,1,2,3}∗ | at least half the symbols comprising w are 0’s} 9. A={s ∈ {a,b,c}∗ | s is a palindrome}. (A palindrome is a string of characters that reads the same forward as backwards — ie., s = reverse(s) for the string s. Examples of palindromes are the words mom, deed, and otto. 10. A={rs∈{0,1,2}∗ | r is a proper prefix of s} Thus 010010112 and 20122012110 are elements of A, but 01002 and 211020111 are not.

For each of the following problems, decide whether the set A is regular. If the set is regular, give a FSM that recognizes it; if the set is not regular, prove it using the pumping lemma 1. A-(slls sE0 Thus the strings 00011000 and 000001100000 are elements of A, but 00100 and 001100000 are not. 2. A-frlls r,sE10 Thus the strings 001100 and 0110000 are elements of A, but 00111100 and 000010 are not 3. A-wea,b)* w contains at least two a's and at most two b's 4. A-we{a,b)* | w contains exactly two more a's than b's 5. A-(30"12"4 >1 Thus 30011224 and 30001112224 are elements of A but 301124, 3001122, 0001112224, and 301224 are not 6. A-30P192 4 | p21, q21, r21) Thus 30124 and 300122224 are elements of A but 30120124, 301122, and 3010124 are not. 7. A-w E 10,1there are 3 times as many 0's as 1's 8. A-w E 0,1,2,3 at least half the symbols comprising w are 0's) 9. A-s e fa,b,c" | s is a palindrome). (A palindrome is a string of characters that reads the same forward as backwards-ie.' s reverse(s) for the string s. Examples of palindromes are the words mom, deed, and otto 10. A-frse10,1,2 r is a proper prefix of s) Thus 010010112 and 20122012110 are elements of A, but 01002 and 211020111 are not

I just need questions 8, 9, 10 to be answered, not all of them.

Answer 1

→£t- es a cfa but not regula. we need Count the OcLrenca. Sinca oce and fa have i emon, Dr occuenca Can he 9 Suphoe So, ii not a RL Not- a pauindrome ex: 이10011023,(eA3 where v 2- Not a Teaulas., a^ Cat decide pto ng