Please answer the following questions. Also, please show all work and Automata.
ID: 671077 • Letter: P
Question
Please answer the following questions. Also, please show all work and Automata.
1. Show that the language of all strings ending in “aa” over the alphabet {a, b} is regular.
a. Find the equivalent deterministic automaton.
2. Find an NFA without £ transitions and with a single final state that accepts the set
{a} U {bn, n>1}
a. Find its equivalent DFA
3. Consider the L(w) = {w {a}*| |w| is divisible by either 3 or 5}
a. Show that L(w) is regular.
b. Find a regular expression that corresponds to this language.
Explanation / Answer
Automata theory is basically about the study of different mechanisms for generation and
recognition of languages. Automata theory is basically for the study of different types of
grammars and automata. A grammar is a mechanism for the generation of sentences in a
language. Automata is a mechanism for recognition of languages. Automata theory is mainly for
the study of different kinds of automata as language recognizers and their relationship with
grammars.
In theoretical computer science, automata theory is the study of abstract machines and problems
they are able to solve. Automata theory is closely related to formal language theory as the automata are
often classified by the class of formal languages they are able to recognize.