Scribd
Upload
53 views3 pages

DFA Exercises

The document outlines exercises related to Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA), including tasks to determine accepted strings, draw state diagrams, and convert NFAs to equivalent DFAs. It also includes requests for regular expressions for specific languages and the output for various regular expressions. The exercises cover a range of topics within automata theory and formal languages.

Uploaded by

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

DFA Exercises

The document outlines exercises related to Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA), including tasks to determine accepted strings, draw state diagrams, and convert NFAs to equivalent DFAs. It also includes requests for regular expressions for specific languages and the output for various regular expressions. The exercises cover a range of topics within automata theory and formal languages.

Uploaded by

almudharisaleh8
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

DFA Exercises.

Determine which of ", 11, 010, 10, 0101 is accepted by this DFA.

The DFA state diagram below is defined on the alphabet ∑ = {𝑎, 𝑏, 𝑐} = {a, b,
c}. Write out its formal definition (as a 5-tuple). When specifying the transition
function 𝛿 , draw a table.

Draw a DFA that recognizes:


(a) All strings with the prefix 01
(b) L = {11, 101, 010, 0110}.

NFA Exercises
Draw an NFA that recognizes:
(a) All strings that contain 101
(b) L = {w 2 {0, 1}⇤| w has exactly two 0’s or an even number of 1’s}.
(c) L = {All strings that contain exactly three a's}
(d) L = {All strings that end with ab}
(e) L = {All strings in which letter a is even number}
(f) L = {All strings that contain exactly two successive a's.}

Convert the following NFA to its equivalent DFA

𝜀
a
𝜀 2 3 𝜀 𝜀 a b
𝜀 b 1
0 1 6 7 8 9 0
𝜀 𝜀
4 b 5
𝜀

Find a regular expression over the alphabet {a, b} :


a. L1 = {All strings that contain exactly three a's}
b. L2 = {All strings that end with ab}
c. L3 = {All strings in which letter a is even number}
d. L4 = {All strings that contain exactly two successive a's.}
2 -Find the output (words) for the following regular
expressions :
a. aa* b
b. bba*a
c. (a + b)* ba
d. (0+1)* 00 *)1+0(
e. (11 + 0)* (0+11)*
f. 01* + (00+101)*
g. (a+b)* abb+

You might also like