Theory of Computation - Showing that a language is regular..

Question

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!

Answer 1

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.

Answer 2

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.