4200 - Formal Languages: Final Exam Fall 2020

Problem 1

10 points

A = {0, 1, 2}*

B = {0, 1}*

C = A · B

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

Problem 2

10 points

Define a regular expression that recognizes the set A that passwords that satisfy the following criteria:

●  Minimum password length: 2

●  Maximum password length: 4

●  Each character in the password must be one of the following LaTeX: { a, b, c, A, B, C, 1, 2, 3 }

●  Password must contain at least one upper-case letter

●  Password must contain at least one number

Answer:

U = {A, B, C}                                            (2)

N = {1, 2, 3}                                            (3)

α =                                            (4)

NU u UN                                            (5)

u ΣNU u ΣUN u UΣN u UNΣ u NΣU u NUΣ                                            (6)

Problem 3

15 points

Given a language   E = {1n 0m 02n＋1  | n, m > 0 }. Please answer the following questions:

1. Is the above language regular or non-regular?

Answer:  This is NOT regular.  To prove it using Pumping Lemma, one can use an counterexample

string: s = 1p 02p0 and reach contradiction by using i = 0.                                                                        That is, because |xy| < p, y must contain only 1’s.  Therefore, when we pump down (i.e., set i = 0), xy0 z = xz  E because the number of 1’s is less than half of the number of 0’s.

2. Is the above language context-free or not?

3. Is the above language Turing-recognizable or not?

4.  Based on your answers to the above questions, please answer one of the following:

a. If you answer E is regular and context-free, please provide an NFA or a regular expression that recognizes E .

b.  If you answer E is regular and NOT  context-free, please provide a proof (showing E is not context-free) using Pumping Lemma for Context-free Languages.

c.  If you answer E is NOT regular and  context-free, please provide a proof (showing E is not regular) using Pumping Lemma for Regular Languages.

d.  If you answer E is NOT regular and NOT context-free, please provide a proof (showing E is not context-free) using Pumping Lemma for Context-free Languages.

Problem 4

15 points

Given a language  G = {1北 0y 1北 0y  | x, y > 0 }  n  {1k 0n 1k 0v  | k, v, n > 0 }.

Please answer the following questions:

1. Is the above language regular or non-regular?

Answer:

G = {1北 0y 1北 0y  | x, y > 0 }  n  {1k 0n 1k 0v  | k, v, n > 0 }

= {1北 0n 1北 0v  | x, v, n > 0}

This is NOT regular.   To prove it using Pumping Lemma, one can use an counterexample string: s = 1p 01p  and reach contradiction by using i = 0 (similar to the proof in Problem 3.1 in the previous page).

2. Is the above language context-free or not?

3. Is the above language Turing-recognizable or not?

4.  Based on your answers to the above two questions, please answer one of the following:

a. If you answer G is regular and context-free, please provide an NFA or a regular expression that recognizes G.

b.  If you answer G is regular and NOT  context-free, please provide a proof (showing G is not context-free) using Pumping Lemma for Context-free Languages.

c.  If you answer G is NOT regular and  context-free, please provide a proof (showing G is not regular) using Pumping Lemma for Regular Languages.

d.  If you answer G is NOT regular and NOT context-free, please provide a proof (showing G is not context-free) using Pumping Lemma for Context-free Languages.