1. Homepage
2. Programming
3. Computer Science 350 Automata and Formal Languages Assignment 1: Automata

# Computer Science 350 Automata and Formal Languages Assignment 1: Automata

Computer Science 350CS350Automata and Formal LanguagesAutomata

Computer Science 350 (2023)

# Assignment 1: Automata

This assignment is worth 100 marks representing 10% of your total course grade.

Solutions must be typed. Respect the academic integrity obligations.

Questions Question A Consider the following NFA N :

a) What is the language accepted by the NFA N ? b) Construct an NFA N1 which accepts the language {an bwb | n ≥ 0, w ∈ {a, b}∗ }. c) Modify N1 such that the language accepted by the new NFA N2 is {an bw | n ≥ 0, w ∈ {a, b}∗ }. d) Construct a DFA M such that L(M ) = L(N2 ). [20 marks]

Question B Consider the sequence of languages Ln = {an bn }, n > 0. a) Fix n. Is the language Ln = {an bn } regular? S b) Let N > 0 be an integer. Is the language L = N n=1 Ln inﬁnite? c) Is the language L regular? S∞ d) Is the language R = n=1 Ln inﬁnite? e) Is the language R regular? Justify all answers. [50 marks]

Question C Consider the language L = {an bm | 0 < n < m or 0 < m < n}. a) Find an error in the following “Proof” that L is not regular: We have L = {an bm | n 6= m, n, m > 0} = {an bn | n > 0}. We know that the language {an bn | n > 0} is not regular, so since the class of regular languages is closed under complement, L can not be regular (since L regular would imply that {an bn | n > 0} is regular). b) Does the wrong proof given for a) imply that L is regular? c) Is L regular? Justify all answers. [30 marks]

## Get Expert Help On This Assignment

#### Scan above qrcode with Wechat

Computer Science 350代写,CS350代写,Automata and Formal Languages代写,Automata代写,Computer Science 350代编,CS350代编,Automata and Formal Languages代编,Automata代编,Computer Science 350代考,CS350代考,Automata and Formal Languages代考,Automata代考,Computer Science 350help,CS350help,Automata and Formal Languageshelp,Automatahelp,Computer Science 350作业代写,CS350作业代写,Automata and Formal Languages作业代写,Automata作业代写,Computer Science 350编程代写,CS350编程代写,Automata and Formal Languages编程代写,Automata编程代写,Computer Science 350programming help,CS350programming help,Automata and Formal Languagesprogramming help,Automataprogramming help,Computer Science 350assignment help,CS350assignment help,Automata and Formal Languagesassignment help,Automataassignment help,Computer Science 350solution,CS350solution,Automata and Formal Languagessolution,Automatasolution,