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

Posted by Tony on Stack Overflow See other posts from Stack Overflow or by Tony
Published on 2010-04-11T03:58:00Z Indexed on 2010/04/11 4:03 UTC
Read the original article Hit count: 497

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!

© Stack Overflow or respective owner

Related posts about homework

Related posts about computer-science