Reference no: EM132254976
Question 1. Construct a DFA equivalent to the following NFA.
|
a
|
b
|
λ
|
→q0
|
Φ
|
Φ
|
{q1, q4}
|
q1*
|
{q2}
|
Φ
|
Φ
|
q2
|
Φ
|
{q3}
|
Φ
|
q3
|
Φ
|
{q1}
|
Φ
|
q4
|
{q4}
|
Φ
|
{q5}
|
q5*
|
Φ
|
{q6}
|
Φ
|
q6
|
{q5}
|
Φ
|
Φ
|
Question 2. Consider a water bottle vending machine as a finite-state automaton. This machine is designed to accept coins of Rs. 2 and 5 only. It dispenses a single water bottle as soon as the amount entered is equal to or greater than Rs. 12. Coins may be inserted in any order and the machine returns appropriate amounts of change (Note: it returns a chocolate in place of one rupee change). However, there is no cancel button to get back the coins without completing the transaction. What is the exact number of states needed in this automaton? Show the automaton.
Question 3. The DFA M accepts a Language L over some alphabet Σ with distinct start state qs and a single final state qf.
i) What happens to L(M) if we introduce the following transition?
δ(qs , x) = qs for ∀ x ?Σ
You may express this formally using set theoretic notations or precisely in English.
ii) Would the automaton be still a DFA? Why?
Question 4. Construct FSM for the following scenarios.
Input: non empty binary sequence
I) output:
Should end in a final state if the input stream has a 1. So your automaton should mimic OR operation.
ii) output:
Should end in a final state only if the input stream has only a sequence of 1 and no 0. So your automaton should mimic AND operation.
Question 5. Write a regular expression for the following language:
L = {w ? {0, 1}* | w contains an equal number of occurrences of the substring 01 and 10}
(Eg. 010 ? L because 010 contains a single 01 and a single 10 as substrings; but 01101 doesn't belong to L because 01101 contains two 01 s and one 10.
Question 6. Consider the finite automaton given by the diagram. Is this automaton deterministic? Using a standard method construct a regular expression for the language defined by the automaton.
![1721_figure.jpg](https://secure.expertsmind.com/CMSImages/1721_figure.jpg)
Question 7. Minimize the DFA with the set of states {1, 2, 3, 4, 5, 6, 7, 8}, input alphabet Σ = {a, b} initial state 1, final states {3, 4} and the transition function given by the table:
![707_figure1.jpg](https://secure.expertsmind.com/CMSImages/707_figure1.jpg)
Let L be the language accepted by this DFA. Consider the equivalence relation RL on Σ* (thus RL⊆Σ* × Σ*) defined by: xRLy if and only if for all z ∈Σ*, xz∈ L iffyz∈ L. What is the index (the number of equivalence classes) of RL? Describe precisely at least one of the equivalence classes of RL (by giving an automaton, or a regular expression).
Question 8. Find a regular expression for the language L = {w ? {a, b}*: na(w) is even &nb(w) is odd}.
Question 9. Show that the language of binary strings of even length having the same number of 0s in its two halves is not regular.
Question 10. To show that Language containing equal number of a and b, can we select the string w as follows.
What could the adversary do in each case?
i) w = (ab)m
ii) w = am/2bm/2
What is the role of technology in project management
: What is the role of technology in project management and expectations for the development of the project management field aided by modern technologies.
|
Identify a state health policy and the tools
: Identify a state health policy and the tools used to implement the policy. How do you think the political climate has affected the choice of policy tools.
|
Is the information in the segment table consistent
: Is the information in the segment table consistent? If there are possible errors that you identify, what will their implication be?
|
Prepare entries to record the sale of the copiers
: Prepare entries to record the sale of the copiers, the related warranty costs, and any accrual on December 31, 2017
|
Find a regular expression for the language
: Theory of Computation – UE17CS254 - Show that the language of binary strings of even length having the same number of 0s in its two halves is not regular
|
Prepare the single-step income statement for the fiscal year
: The following is the Easton Company adjusted Trial Balance. Use this information to prepare the Single-Step Income Statement for the fiscal year
|
Examining the behaviors and characteristics of people
: NURS 6052 – Essentials of Evidence-Based Practice Research is a process of evaluating a concept or theory concerning a specific subject.
|
Steps are required for anyderivation
: Show that if G is a Context Free Gramamr in Chomsky normal form, then for any string ?? L(G), |?|=n=1, then exactly 2n-1 steps are required for anyderivation of
|
Salesorderheader and salesterritory
: Display salesorderid, orderdate, totaldue, and territory name from salesorderheader and salesterritory for all totaldue that are greater
|