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: 495

Filed under:

homework

|

computer-science

|

finite-automata

|

regular-language

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

parsing a list and producing a structure of that

as seen on Stack Overflow - Search for 'Stack Overflow'
;; structure representing homework points ;; nr: number - the number of the homework ;; points: number - the number of points reached (define-struct homework (nr points)) ;; parse-homework: (list of number pairs) -> (list of homework) ;; The procedure takes a list of number pairs and produces… >>> More
Scheme homework help

as seen on Stack Overflow - Search for 'Stack Overflow'
Okay so I have started a new language in class. We are learning Scheme and i'm not sure on how to do it. When I say learning a new language, I mean thrown a homework and told to figure it out. A couple of them have got me stumped. My first problem is: Write a Scheme function that returns true (the… >>> More
Unix [Homework]: Get a list of /home/user/ directories in /etc/passwd

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm very new to Unix, and currently taking a class learning the basics of the system and its commands. I'm looking for a single command line to list off all of the user home directories in alphabetical order from the /etc/passwd directory. This applies only to the home directories, and not the contents… >>> More
sequential search homework question

as seen on Stack Overflow - Search for 'Stack Overflow'
Consider a disk file containing 100 records a. How many comparisons would be required on the average to find a record using sequential search, if the record is known to be in the file? I figured out that this is 100/2 = 50. b. If the record has a 68% probability of being in the file, how many comparisons… >>> More
[Homework] Online programming editor

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, For a school project i need to write or use a online programming editor. It is a part of a bigger project. I thought of a java application, php/html/javascript or flash. I have a couple of things i could do: Find a good working application and edit it so it works with the rest of the project Find… >>> More

Related posts about computer-science

How do I completely self study computer science?

as seen on Programmers - Search for 'Programmers'
Being a completely self taught programmer I would like it if I could better myself by self-learning computer science course taught to a typical CS grad. Finding different resources on internet has been easy, there is of course MIT open course ware, and there are Coursera courses from Stanford and… >>> More
what, why, when, should I learn computer science?

as seen on Programmers - Search for 'Programmers'
I'm 16 years old and really an enthusiast on web programming. I know (X)HTML, css, javascript and php. And i heard about computer science. Below are my question: What is computer science? Should a web programmer learn computer science? If the answer of question 2 is yes, then what programming language(s)… >>> More
what, why, when, should I learn computer science?

as seen on Programmers - Search for 'Programmers'
I'm 16 years old and really an enthusiast on web programming. I know (X)HTML, css, javascript and php. And i heard about computer science. Below are my question: What is computer science is? Should a web programmer learn computer science? If the answer of question 2 is yes, then what programming… >>> More
What topic in computer science is this?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I am trying to figure out what 'topic' this is called, so I can learn more about it. Basically, I'm talking about designing my applications's architecture. I'm not talking about algorithms. More like -- this class should have these methods and these instance variables, and communicate with… >>> More
Computer Science Resume [closed]

as seen on Stack Overflow - Search for 'Stack Overflow'
I am looking for a good computer science resume. I just graduated, and I would like to see some samples from real programmers. The ones online don't seem that great. Sorry if this is posted in the wrong section. >>> More