n this problem, we only consider automata without epsilon transitions. A clipping of an NFA N is a DFA obtained by the following process: for each state-letter pair (q, x) where q ∈ Q, x ∈ Σ, if |δ(q, x)| > 1, choose one element of it to be δ(q, x) and ignore the rest. Note that an NFA may have many possible clippings. 1. Consider the following claim: “For every epsilon-free NFA N and string x, the NFA N accepts x if and only if some clipping of N accepts x.” This claim is false. Show that it is false by providing a counterexample. (Aside: It turns out that deciding whether N accepts x is in P, while deciding whether some clipping of N accepts x is NP-complete, which you will learn about later in the course. Hence, if the claim were true, it would imply that P = NP.) An automaton A over the alphabet Σ is universal if it accepts every string, that is, if L(A) = Σ∗. 2. Consider the following claim: “For every epsilon-free NFA N, the NFA N is universal if and only if some clipping of N is universal.” This claim is also false. Show that it is false by providing a counterexample. In both of these questions, each counterexample should: • be over the alphabet Σ = {a, b}, • have no more than 10 states, and • have no more than 10 clippings

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

In this problem, we only consider automata without epsilon transitions. A clipping of an NFA N is a DFA obtained by the following process: for each state-letter pair (q, x) where q ∈ Q, x ∈ Σ, if |δ(q, x)| > 1, choose one element of it to be δ(q, x) and ignore the rest. Note that an NFA may have many possible clippings. 1. Consider the following claim: “For every epsilon-free NFA N and string x, the NFA N accepts x if and only if some clipping of N accepts x.” This claim is false. Show that it is false by providing a counterexample. (Aside: It turns out that deciding whether N accepts x is in P, while deciding whether some clipping of N accepts x is NP-complete, which you will learn about later in the course. Hence, if the claim were true, it would imply that P = NP.) An automaton A over the alphabet Σ is universal if it accepts every string, that is, if L(A) = Σ∗. 2. Consider the following claim: “For every epsilon-free NFA N, the NFA N is universal if and only if some clipping of N is universal.” This claim is also false. Show that it is false by providing a counterexample. In both of these questions, each counterexample should: • be over the alphabet Σ = {a, b}, • have no more than 10 states, and • have no more than 10 clippings.