1. Which of the following languages are not regular say Regular or Not Regular.
ID: 3586083 • Letter: 1
Question
1. Which of the following languages are not regular say Regular or Not Regular. In each case w E (a, bl*. Also, Include a brief statement justifying your answer (1-2 sentences) A={a"b" I n 10) B = { a"bn I n z 10 and ms 10) a. b. d. D-la"b m and n are both odd numbers | e. E = { an I n is a prime number) 2. Which of the following languages are not regularsay Regular or Not Regular. In each case w E (a, b, c. Also, Include a brief statement justifying your answer (1-2 sentences) f. A = { wcw I w E {a, b)" } g. B w I w is either a"b or ba where m, n 20] j. Eab"a n2 10 and ms 10)Explanation / Answer
1)
a)It is not regular...
because, here the number a's is equal to number of b's,.....means we need to check...whether.. number a's is equal to number of b's or not.... for that we need a stack... Finite automata doesn't have the stack....mean we can't build Finite automata for..it.......hence it is not regular...
b)it is regular...
because there is comparision between a's and b's,,means we don't need a stack here, there is only length restrictions on a's and b's, so we can build FA(Finite automata) for it.... hence it is regular...
c)it is not regular...
because, here the number a's is not equal to number of b's,.....means we need to check...whether.. number a's is equal to number of b's or not.... for that we need a stack... Finite automata doesn't have the stack....mean we can't build Finite automata for..it.......hence it is not regular...
d) it is regular....
because there is comparision between a's and b's,,means we don't need a stack here, we can individually by states can check whether they are odd or not, so we can build FA(Finite automata) for it.... hence it is regular.
e)it is not regular...
because/// to check prime or not...we need to find factors....means we need a stack..
hence not regular...
2)
f)it is regular...
we can write regular expression for. . it. (a+b)*c(a+b)* ..hence its is regular
g)it is regular....
because there is no comparision between a's and b's
h)it is not regular...
becauser...here number of a's == number of b's == number of c's.... to check this is we need stack
i)it is regular..
no comparision is there between a,b,c
j)it is not regular..
number of a's in the begining should be equal to number of a's in the ending, to check this we need a stack..
hence not regular...
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.