deleted 2. Converting a DFA such as the following to a regular expression requir

Question

deleted

2. Converting a DFA such as the following to a regular expression requires us to develop regular expressions for limited sets of paths -- those that take the automaton from one particular state to another particular state, without passing through some set of states. For the automaton above, determine the languages for the following limitations: 1. LAA the set of path labels that go from A to A without passing through C or D 2, LAB = the set of path labels that go from A to B without passing through C or D 3. LBA the set of path labels that go from B to A without passing through C or D 4.LBB = the set of path labels that go from B to B without passing through C or D Then, identify a correct regular expression from the list below. Note: there are several different regular expressions possible for each of these languages. However, each of the correct answers can be thought of as built from more limited components. For example, the regular expression 1 is the set of path labels that go from A to B without passing through any of the four states. o a) LAR 0 1(00*1* b) LA 0 1(01+10)* C) LBB 000*)* d) LBA= (01+0)*

Explanation / Answer

a) True.

We can reach B from A with 0*1. After reaching B, we can always come back to B via A with 00*1. So L(AB) will be 0*1(00*1)*

b) False.

We can reach B from A with 0*1. But after that if we use 10, we will go to C and then come back to B. But C should not be traversed.

c) False

Let us take 0 as an example string from 0(0*1)*. We will reach A from B with 0, but we should reach B, so false.

d) False.

Let us take 01 as an example string from (01+0)*. We will reach A from B with 0, then we again reach B with 1. But we should reach A, so false.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.