3) (20 points) Select (circle) an answer of true or false for each of the follow

Question

3) (20 points) Select (circle) an answer of true or false for each of the following If a language is accepted by a DFA then there exists an NFA that accepts that language as well. If a language is not accepted by any NFA, then that language is not accepted by any NFA-e. Every finite language is regular. Every regular expression represents an infinite language. Every state in a valid DFA must be reachable from the start state. The transition function for a DFA must be a total function. Given an NFA and a string, there can be an infinite number of paths (i.e, computations) through the NFA T F labeled with that string. Epsilon transitions greatly expand the power of NFAs. Induction expressions. is a proof technique that applies very naturally to recursively defined structures such as regulsr The hypothesis in a weak inductive proof assumes more than one in a strong inductive proof.TF 4) (10 points) Give a DFA that accepts the set of all strings over (0,13 that begin with a l, end with a 0, and contain at least three symbols. For example, some strings accepted by the DFA would include 10010, 100, 1100 and 110011010. Some strings not accepted by the DFA include 10, 01110, 1101, 111, and e

Explanation / Answer

Solution :

1. True
if a language is accepted by DFA then it is a regular language and each DFA is NFA too.

2. True
NFA and NFA with null has same expressing power.

3. True
There is a DFA that accepts each finite language. Hence all finite languages are regular.

4. False
A regular expression can also represent finite language.

5. False.
There can be states in DFA that are not reachable from start state and DFA could still be valid.

6. True
For a DFA, transaction has to be defined for each state for all inputs.

7. False
NFA has finite number of states, so it can not have infinite number of ways to parse string.

8. False
epsilon transaction doesnt increase the power of NFA.

9. True

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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