4200 - Formal Languages: Final Exam Fall 2019

Problem 1

10 points

Alphabet Σ = {0, 1}.

A = {0, 1}*

B = L(α)

where α is a regular expression: α = 0* n 1*

C = A u B

For each of the languages (A, B , B , and C), write down five example strings in it. Construct a deterministic finite automaton (DFA) that recognizes the language C .

Problem 2

10 points

Define a nondeterministic finite automaton (NFA) M such that L(M) = L(β) where β is a regular expression:

β = (1 > e)* > 11* e(0 > 1) > e

Note:  for grading purposes, please do NOT simplify the given regular expression before constructing the NFA.

Problem 3

10 points

Write down a context-free grammar for the following language D . Please use S as the start variable. D = { 1北＋2y0北 1y  l 北, y ● 0 }

Problem 4

20 points

Is there a decidable Turing machine that accepts the following language D?  (i.e.  a Turing machine that halts for every input).

D = { 1北＋2y0北 1y  l x, y ● 0 }

· If yes, please describe in English how this Turing machine works (as if you were trying to convince a friend that this algorithm works).  In addition to the English description, transition diagrams are optional (if you think it helps explaining), but not required.

· If no, please explain why.

Problem 5

10 points

Is the language D in Problem 4 regular or not?

D = { 1北＋2y0北 1y  l x, y ● 0 }

If yes, please show that via a DFA/NFA or a regular expression. If not, please prove it via pumping lemma for regular languages.

Problem 6

10 points

E = { 1北＋2y0北 1y 1y  l x, y ● 0 }

Please answer Yes or No.

· Is the language E regular?

· Is the language E context-free?

· Is the language E Turing-decidable?

· Is the language E Turing-recognizable?