Tutorial 4

Tutorial questions

==Subjective questions==

1. Define the following terms:
   1. a) Automaton
   2. b) Alphabet
   3. c) String
   4. d) Language
2. Given an alphabet Σ = {a, b}, list some valid strings over Σ.
3. Explain why we need a simpler way of discussing computing machines.
4. Describe the concept of an automaton and its role as a mathematical model of a com- puting device.
5. What are the reasons for building models in computing? Explain the significance of finite automata as abstractions of computers
6. Define an alphabet and a string over an alphabet Σ. Provide examples.
7. Given an alphabet Σ = {a, b, c}, list some valid strings in the language of palindromes over Σ.

Objective questions

1. Define an NFA and explain how it differs from a DFA in terms of determinism.
2. Define the formal structure of a DFA and NFA (hint: look at the 5 tuple structure I disucssed in the lecture).

Design DFA

Design NFA

More practice questions

Tutorial sheet