Problem 1

Make sure you read the lecture notes below so you understand this problem! Consider the machine M defined below.

Write down a sequence of configurations representing possible computational paths for this machine and the input string cbcaa that ...

1. reads all input and ends in an accepting state
2. reads all input and ends in a non-accepting state
3. gets stuck before it gets all the input read

Problem 2

Give a concise english description of the language accepted by this Non-Deterministic Finite Automaton.