Q1: Explain the differences between DFA and NFA, in the theory of computation with at least two (2) relevant practical e
Posted: Thu May 05, 2022 12:54 pm
Q1: Explain the differences between DFA and NFA, in the theory of computation with at least two (2) relevant practical examples of each.
Q2.Give a formal definition of the string accepted by an NFA and ε-NFA
Q3. Design a DFA that accepts all strings over {0, 1} that have 101 as a substring, where k is a substring of w if there are w1 and w2 such that w = w1 k w2.
Q4. Convert the DFA in Q3 above to an equivalent NFA
Q5. Below is an ε-NFA that models a new vending machine proposed at Legon Supermarket;
a) Determine the set of substrings accepted by the ε-NFA above
b) Determine the ε-closure of all possible states of the ε-NFA above
c) Derive the state transition table associated with the ε-NFA above
Q2.Give a formal definition of the string accepted by an NFA and ε-NFA
Q3. Design a DFA that accepts all strings over {0, 1} that have 101 as a substring, where k is a substring of w if there are w1 and w2 such that w = w1 k w2.
Q4. Convert the DFA in Q3 above to an equivalent NFA
Q5. Below is an ε-NFA that models a new vending machine proposed at Legon Supermarket;
a) Determine the set of substrings accepted by the ε-NFA above
b) Determine the ε-closure of all possible states of the ε-NFA above
c) Derive the state transition table associated with the ε-NFA above