1 of 18

Quiz – Version 1

Write your Name, Student ID, and section number on a piece of paper

2 of 18

Time limit – 30 minutes

  • Write a regular expression that matches with a hexadecimal number. Hexadecimal numbers optionally end with either an h or H. �At least one hexadecimal digit should exist.
  • Find an NFA and a DFA for the following language

a | a a* b

​

3 of 18

Solution

  • Hexa := ([0-9]|[A-F])+ (h|H)?
  • NFA

​

  • DFA

a

a

4 of 18

Quiz – Version 2

Write your Name, Student ID, and section number on a piece of paper

5 of 18

Time limit – 30 minutes

  • Write a regular expression to the following language, �Σ = {a, b, c}, L = {W ∈ Σ* | all the a’s come before any occurrence of c}.
  • Find an NFA and a DFA for the following language

(a | ba)*bb(a | ab)*

6 of 18

Solution

  • RE := (a|b)* (b|c)*
  • NFA
  • DFA

​

​

​

  • DFA - Another solution

7 of 18

Quiz – Version 3

Write your Name, Student ID, and section number on a piece of paper

​

8 of 18

Time limit – 30 minutes

  • Write a regular expression to the following language, �Σ = {a, b, c}, L = {W ∈ Σ* | where a palindrome substring of length 2 is in the middle of W}.
  • Find an NFA and a DFA for the following language

(bb)*(aa)*

9 of 18

Solution

  • RE := (a|b|c)*(aa|bb|cc)(a|b|c)*
  • NFA

​

  • DFA

​

​

​

​

  • DFA with trap state

10 of 18

Quiz – Version 4

Write your Name, Student ID, and section number on a piece of paper

11 of 18

Time limit – 30 minutes

  • Determine the regular expression for the language accepted by the following automaton.

​

​

  • Find an NFA and a DFA for the following language

Σ = {0, 1}

L = { w ∈ Σ* | w contains at most one 0 }

12 of 18

Solution

  • RE := 1(1|01*0)*
  • NFA – re := 1* 0? 1*

​

  • DFA

13 of 18

Quiz – Version 5

Write your Name, Student ID, and section number on a piece of paper

14 of 18

Time limit – 30 minutes

  • Determine the regular expression for the language accepted by the following automaton.

​

​

​

  • Find an NFA and a DFA for the following language

(ab|abb)+ (b)?

15 of 18

Solution

  • RE := a* b
  • NFA

​

  • DFA

q0

q0

, b

16 of 18

Quiz – Version 6

Write your Name, Student ID, and section number on a piece of paper

17 of 18

Time limit – 30 minutes

  • Determine the regular expression for the language accepted by the following automaton.

​

​

  • Find an NFA and a DFA for the following language

NFA for [a-z]*car[a-z]?

DFA for [a-z]*car

18 of 18

Solution

  • RE := b* a a* a b* a� or b* a+ a b* a

​

  • NFA – re = [a-z]*car[a-z]?
  • DFA – re = [a-z]*car

q0