1. Engineering
  2. Computer Science
  3. 3 suppose that l is a language accepted by a...

Question: 3 suppose that l is a language accepted by a...

Question details

3. Suppose that L is a language accepted by a transition graph T with one start state and one final state. Also suppose that L does not contain the word ab. We want to build a new TG that accepts exactly L and the word ab. On the next page, you will find two example TGs that you may use to help you answer parts (a) and (b), and that you must use in part (c) (a) One suggestion is to draw an edge from - to and label it ab. Show that this does not always work. (b) Another suggestion is to draw a new state and draw any edge from any state to it labeled ab. Show that this does not always work. (c) Give an algorithm that does work. In other words, describe a series of steps that can be used to transform a TG that accepts L to a new TG that accepts LU tab). Show the result of applying your algorithm to the two transition graphs on the next page.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution