GATE 2008
March 14, 2025GATE 2008
March 14, 2025GATE 2008
|
Question 53
|
Which of the following are regular sets?
- I. {anb2m | n≥0, m≥0}
II. {anbm | n=2m}
III. {anbm | n≠2m}
IV. {xcy | x,y∈{a,b}*}
|
I and IV only
|
|
|
I and III only
|
|
|
I only
|
|
|
IV only
|
Question 53 Explanation:
Statement I represents a regular language whose regular expression is a* (bb)*. Also it doesn’t require any comparison between “a” and “b” , so it can be recognized by DFA and hence regular.
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Correct Answer: A
Question 53 Explanation:
Statement I represents a regular language whose regular expression is a* (bb)*. Also it doesn’t require any comparison between “a” and “b” , so it can be recognized by DFA and hence regular.
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.