What is regular expression corresponding to the language of strings of...
The regular expression corresponding to the language of strings of even lengths over the alphabet of {a, b} is ((a + b)2)* which is equivalent to (aa + bb + ba + ab)*. In choice (b) the string ‘ab’ is not present. In choice (c) the string ‘aa’ is not present. In choice (d) odd length strings are also acceptable.
View all questions of this test
What is regular expression corresponding to the language of strings of...
Regular expression for even length strings over {a, b}
Regular expressions are a sequence of characters that form a search pattern. In computer science, regular expressions are used to match patterns in strings. The regular expression corresponding to the language of strings of even lengths over the alphabet of {a, b} is (aa bb ba ab)*.
Explanation:
The regular expression (aa bb ba ab)* matches strings that contain zero or more occurrences of the four strings aa, bb, ba, and ab. Since the language we are interested in is the language of strings of even lengths over {a, b}, the regular expression (aa bb ba ab)* is a good candidate for matching such strings.
Here is why:
- The regular expression matches strings that contain only the characters a and b since these are the only characters in the alphabet.
- The regular expression matches the empty string since it contains zero occurrences of aa, bb, ba, and ab.
- The regular expression matches strings of even lengths since each occurrence of aa, bb, ba, and ab contributes two characters to the string.
For example, here are some strings that are matched by the regular expression:
- "" (the empty string)
- "aa"
- "bb"
- "baab"
- "bbaaabbaba"
None of these strings contain an odd number of characters, so they are all in the language of strings of even lengths over {a, b}.
Conclusion:
The regular expression (aa bb ba ab)* matches strings that are of even lengths over the alphabet of {a, b}.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).