I'm reviewing some notes for my course on Theory of Computation and I'm a little bit stuck on showing the following statement and I was hoping somebody could help me out with an explanation :)
Let A be a regular language. The language B = {ab | a exists in A and b does not exist in A*} Why is B a regular language?
Some points are obvious to me. If b is simply a constant string, this is trivial. Since we know a is in A and b is a string, regular languages are closed under union, so unioning the language that accepts these two strings is obviously regular. I'm not sure that b is constant, however. Maybe it is, and if so, then this isn't really an issue. I'm having a hard time making sense of it. Thanks!
You can prove by construction: Give a regular expression that recognizes B. The class of regular languages is closed under union, concatenation, star, and complement.
The a
and b
in the question are not constant strings but any strings, and B is the language of strings with the beginning of the string in A and the end of the string not in A. Now, since any regular language can be recognised by a regular expression, if Ra
is the regular expression to recognise the language A, then Ra
concatenated with the “not Ra
” regular expression is the regular expression to recognise the language B. Since B can be recognised by a regular expression, it's a regular language.
Edit: I initially missed the star after the A at the end of the definition of B in the question. To account for it, make the part of the regular expression that recognises b
also include the star.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With