INT201, Assignment 1

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

INT201, Assignment 1

21-22/S1

Question 1

Let Σ = {a,b}. Define A = {w ∈ Σ*  | | w |≥ 2, second-to-last symbol of w is a} (20 marks)

(a) List the first 4 strings in A in lexicographic order. (4 marks)

(b) Draw a DFA for A.(16 marks)

Question 2

Let E, F be regular expressions, and E = 0, F = 1. (20 marks) (a) Give a DFA that accepts E n F . (4 marks)

(b) Give a DFA that accepts EF . (4 marks)

(c) Give a DFA that accepts (E n F)EF . (6 marks)

(d) Give a DFA that accepts (EF)* . (6 marks)

Question 3

Convert the given NFA to its corresponding DFA. (20 marks)

 

Question 4

Design context free grammars for the following languages  (only providing rules). (20 marks)

(a) The set {an  | n ≥ 1} (6 marks)

(b) The set {0n 1n  | n ≥ 1} (6 marks)

(c) The set {ai bj ci e2  | i,j ≥ 0} (8 marks)

Question 5

Let Σ = {a,b}, and consider the language A = {w ∈ Σ*  | w has more b′ s than a′ s}. (20 marks)

(a) Describe pumping lemma for regular languages. (4 marks)

(b) Prove that A is not a regular language. (16 marks)


2023-01-06