Scribd
Upload
3 views3 pages

DFA Design and Conversion Tutorial

The document outlines a tutorial from the Thapar Institute of Engineering and Technology, focusing on designing Deterministic Finite Automata (DFA) for various conditions related to strings over specified alphabets. It includes tasks such as creating DFAs that accept strings based on specific ending patterns, substring restrictions, and evenness of letters, as well as converting Non-deterministic Finite Automata (NFA) to DFA. Additionally, it requires finding minimum length strings not represented by certain regular expressions and drawing finite automata for given regular expressions.

Uploaded by

praneethsimon2004
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
3 views3 pages

DFA Design and Conversion Tutorial

The document outlines a tutorial from the Thapar Institute of Engineering and Technology, focusing on designing Deterministic Finite Automata (DFA) for various conditions related to strings over specified alphabets. It includes tasks such as creating DFAs that accept strings based on specific ending patterns, substring restrictions, and evenness of letters, as well as converting Non-deterministic Finite Automata (NFA) to DFA. Additionally, it requires finding minimum length strings not represented by certain regular expressions and drawing finite automata for given regular expressions.

Uploaded by

praneethsimon2004
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

Tutorial 3

Thapar Institute of Engineering and Technology Patiala

Computer Science and Engineering Department (CSED)


1. Design a DFA over {a, b} that accepts only those words that do not end with ba.

2. Design a DFA over {0,1} that accept all strings not containing substring 00 .

3. Design a DFA over {0,1} that accepts all strings not containing even number of letters.

4. Design a DFA that accepts only those words that begin or end with a double letter.

5. Convert each of the following NFA’s in to DFA’s.

(a)

a,b

b
B
AA

(b)

a, b

a b b
C D
A B

(c)

a, b

a b
A C
B
(d)

a,b
A C
B

a,b

(e)

a
B
b

a
A
a
a
C

6. Find a string of minimum length in {0,1} not in the language corresponding to the given
regular expression.

a. 1* (01)* 0*

b. 1* (0 + 10)*1*

c. (0* + 1* )(0* + 1* )(0* + 1* )

7. For each of the following regular expressions, draw an FA recognizing the corresponding
language.

(a) (0 + 1)* (1 + 00)(0 + 1)*


(b) (11 + 10)*

(c) (0 + 1)* 0

You might also like