Scribd
Upload
2 views2 pages

Additional Problems

The document outlines a series of tasks involving the conversion of various Non-deterministic Finite Automata (NFA) into equivalent Deterministic Finite Automata (DFA). Each task specifies the alphabet, states, start and final states, and transitions for the NFAs, along with the requirement to perform the conversion. The document includes five distinct problems, each focusing on different NFAs and their respective conversion processes.

Uploaded by

avangame
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views2 pages

Additional Problems

The document outlines a series of tasks involving the conversion of various Non-deterministic Finite Automata (NFA) into equivalent Deterministic Finite Automata (DFA). Each task specifies the alphabet, states, start and final states, and transitions for the NFAs, along with the requirement to perform the conversion. The document includes five distinct problems, each focusing on different NFAs and their respective conversion processes.

Uploaded by

avangame
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Additional Problems

1. Given NFA:
Alphabet: {0,1}
States: {q0, q1}
Start: q0
Final: {q1}
Transitions:
o q0 —0→ q0
o q0 —1→ q0, q1
o q1 —1→ q1
Task: Convert to equivalent DFA.

2. Given NFA:
Alphabet: {a, b}
States: {s0, s1}
Start: s0
Final: {s1}
Transitions:
o s0 —a→ s1
o s0 —b→ s0
o s1 —a→ s1
o s1 —b→ s1
Task: Convert this NFA to a DFA that accepts the same language.

3. NFA
Alphabet: {0,1}
States: {p0, p1, p2}
Start: p0
Final: {p2}
Transitions:
o p0 —0→ p1
o p1 —0,1→ p1
o p1 —1→ p2
o p2—0,1→ p2
Task: Convert this ε-NFA to an equivalent DFA.
4. NFA that accepts strings ending in "ab":
Design an NFA for the language over {a, b} that ends in "ab".
Task: Convert this NFA to a DFA.

5. NFA:
Alphabet: {x, y}
States: {A, B, C}
Start: A
Final: {C}
Transitions:
o A —x→ B
o A —x→ C
o B —y→ C
Task: Convert this NFA to an equivalent DFA using subset
construction.

You might also like