‌CS3331 – Assignment 2 due Oct. 24, 2024

2-day no-penalty extension until: Oct. 26, 11:59pm1

1. For each of the following languages, L, prove whether L is (i) regular, (ii) context-free but not regular, or (iii) not context-free:

   1. L = {xyxR | x, y ∈ {0, 1}+}.

   2. L = {w ∈{0, 1}∗ | every second character of w is a 0 and every third character of w is a 1}.

   3. L = {xay | x, y ∈ {a, b}∗, x is a prefix of y}.

   4. L = {(abb)na(bba)n | n ≥ 0}.

   5. L = Pref({anbm | n ≥ m ≥ 0}). (Pref(L) denotes the set of prefixes of strings in L.)

   6. L = ∅.

   7. For each regular language, L, in the above questions, fully describe the classes of ≈L.

2. For two languages L1, L2 ⊆ {a, b}∗, does ≈L1 = ≈L2 imply L1 = L2? Prove your answer.

3. Show that the following problem is decidable: Given a context-free language, C, and two regular languages, R1, R2, is there a string in C which has a prefix which is in R1 but not in R2?

You are allowed to use any results, algorithms and closure properties proved in class, without proof but you need to indicate clearly what you use. Any new properties, constructions or algorithms should be described in your solution.

Notes: !!! Submit your solution as a single pdf file; anything else receives 0pt. Solutions should be typed but high-quality hand-written solutions are acceptable.

JFLAP: You are allowed to use JFLAP to help you solve the assignment. You still need to explain clearly your solution. Also, make sure you understand what it does; JFLAP will not be available during exams!

LLMs: You are allowed to use LLMs (Large Language Models), such as ChatGPT, but, again, they will not be available during exams.

LATEX: For those interested, the best program for scientific writing is LATEX. It is far superior to all the other programs, it is free, and you can start using it in minutes; here is an introduction: https://tobi.oetiker.ch/lshort/lshort.pdf. It is also available online at https://www.overleaf.com/.