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

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.

Answer 2

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 3

B is a regular language because it is language that ends when a input "b" appear. we can write a regular expression for the given language B as a*b

友情链接