560-PS1-Ravi-Gattamaneni.doc

docx

School

University of Massachusetts, Boston *

*We aren’t endorsed by this school

Course

200

Subject

Computer Science

Date

Dec 6, 2023

Type

docx

Pages

Uploaded by HighnessQuail3665

CIS 560: Theoretical Computer Science Problem Set 1 Submission date: 28 th September 2023 Group Members: Sai Alekhya Ravi (Group leader) Preetham Sai Gattamaneni

Problem 1-1. Design of DFA (2 points) Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}. c. {w| w contains neither the substrings ab nor ba} Answer: Consider, The complement of simpler language = L’ The simpler language= L L’= {w| w contains neither the substrings ab nor ba} L= {w| w contains either the substrings ab or ba} L= {ab,ba,aab,aba,bab,bba,babb,bbab,baba…} DFA for the simpler language L is, Constructing the DFA for the complement of the simpler language (L’) L’= { ,a,b,aa,bb,aaa,bbb….} ɛ The complement of the simpler language (L’) includes the strings that are not acceptable in the simpler language (L). Therefore, in the DFA state diagram the initial state and the transitions remain the same, however, the final states (accepting state) become non-accepting states and the non- accepting states become the final states (accepting states). Hence,

DFA for the complement of the simpler language L’ is,

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

d. {w| w is any string not in a ∗ b ∗ } Answer: Consider, The complement of simpler language = L’ The simpler language= L L’= {w|w is any string not in a ∗ b ∗ } L= {w|w is any string in a ∗ b ∗ } L= { ,a,b,aa,bb,ab,aaab,abbb,aaabbb…} ɛ DFA for the simpler language L is, Constructing the DFA for the complement of the simpler language (L’) L’= {aba,bab,aabba,bbaab,aaaba,bbbab…} The complement of the simpler language (L’) includes the strings that are not acceptable in the simpler language (L). Therefore, in the DFA state diagram the initial state and the transitions remain the same, however, the final states (accepting state) become non-accepting states and the non- accepting states become the final states (accepting states). Hence, DFA for the complement of the simpler language L’ is,

Problem 1-2. Design of NFA (2 points) Use the construction in the proof of Theorem 1.47 to give the state diagrams of NFAs recognizing the concatenation of the languages described in a. Exercises 1.6 g) 1.6 i) 1.6g) {w|w the length of w is at most 5} 1.6i) {w|w every odd position of w is a 1} Answer: Consider, L1= {w|w the length of w is at most 5} L2= {w|w every odd position of w is a 1} NFA for language L1= N1 NFA for language L2=N2 L1= { ,0,1,00,11,01,10, 000,001,010,011,100,101,110,111…11100,11101,11110,11111} ɛ L2= {1,101,10101,1010101….} NFA for L1, N1= (Q1, Σ, δ1, q1, F1) Q1= {q0,q1,q2,q3,q4,q5} Σ= {0,1} δ1=> Q x Σ= Q q1= q0 F1= {q0,q1,q2,q3,q4,q5} NFA for L2, N2= (Q2, Σ, δ2, q2, F2) Q1= {q0,q1,q2 }

Σ= {0,1} δ1=> Q x Σ= Q q1= q0 F1= {q0} Consider, The concatenation of the L1 and L2 (L1  L2) = L The NFA of language L= N According to the theorem in the Sipser, N = (Q, Σ, δ, q6, F2) Q = {q6} ∪ Q1 ∪ Q2= {q6,q0,q1,q2,q3,q4,q5} Σ= {0,1} q6= initial state F2= {q0,q1,q2,q3,q4,q5} NFA for the concatenation of two languages,

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Use the construction in the proof of Theorem 1.49 to give the state diagrams of NFAs recognizing the star of the languages described in a. Exercise 1.6 b.) {w|w contains at least three 1s} Answer: Consider, L= {w|w contains at least three 1s} L= {111,0111,010101,011111…} NFA for L, Star of the language

Problem 1-3. Regular Languages (1.5 point) For any string w = w1w2 ··· wn, the reverse of w, written wR, is the string w in reverse order, wn ··· w2w1. For any language A, let AR = {wR| w ∈ A}. Show that if A is regular, so is AR. Answer: Given, String= w Reverse string= wR Language= A AR= reverse language= reverse string that belongs in the language A Let us consider the DFA of language A, M= ( Q, Σ, δ, q, F) where, Q= set of states Σ= alphabet δ = transition function=>Q x Σ=Q q= initial state F= final state or accepting state To design DFA for the language AR (reverse of language A), M’= ( Q, ΣR, δ, q, FR) Let us consider an example to prove if A is regular language, so is AR. Let A= {w|w contains strings that start with 1} and Σ= {0,1} A= {1,10,11,101,100,111…} DFA of language A, M= ( Q, Σ, δ, q, F) Q= {q0,q1,q2)

Σ= {0,1} q= {q0} F= {q1} AR= {w|w contains strings that does not start with 1} AR= {0,01,01,011,010,0100,0111…} The DFA of AR, M’= ( Q, ΣR, δ, q, FR) Q= {q0,q1,q2) [the set of states remain the same after reverse of language] ΣR= {0,1} [reverse of alphabet] q= {q0} [remains the same after reverse] FR= {q0,q2} [all the non-accepting states become the accepting states and vice versa] A language is said to be a regular language if we can design or construct a finite automata or regular expression. As you can notice the transitions remain the same for both DFA. Both DFA accept the strings from their respective languages. This proves that if language A is regular, then the reverse of that same language is also a regular language.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Problem 1-4. Regular Expressions (2 points) convert the regular expression to a nondeterministic finite automaton. a. (0 ∪ 1)*000(0 ∪ 1)* Answer: String: 0 String: 00 Using concatenation operation, String: 000 Using concatenation operation, String: 0 ∪ 1 Using union operation, String: (0 ∪ 1) * Using star operation,

String: (0 ∪ 1) * 000 Using concatenation operation, String: (0 ∪ 1) * 000 (0 ∪ 1) * Using concatenation operation,

Problem 1-5. Programming Assignment (2.5 points) Using Java Regular Expression classes (presented in java.util.regex package), write a simple program to validate an input email address. The domain part of the email address can be either “umassd.edu” or “gmail.com”, and the local part (i.e., the user name) must start with a letter ([a-zA-Z]) and may be followed by any word characters ([a-zA-Z_0-9]). The length of the local part must be larger than 5 and less than 10. The email address is not case sensitive. In your program, you must implement the following four methods: boolean validateEmailAddress(String emailAddress) String getLocalPart(String emailAddress) boolean isUmassdAccount(String emailAddress) boolean isGmailAccount(String emailAddress) Include a few test cases in the main method to verify that your implementation for each of the methods satisfies the above requirements. Answer: Refer to the EmailValidator.java file for the code. The output contains a valid email and two invalid emails. The emails were declared invalided due to uppercase and for not following the umassd email format.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Related Documents

SaiAlekhya_CIS602_LabHomework1.docx

Lab_9.docx

d2l.laurentian.ca_d2l_lms_quizzing_user_quiz_submissions_attempt.d2l_isprv=&qi=96832&ai=1786958&isIn

CAP 4611 Midterm review.docx

Decision Tree-Nicolle Ramirez.xlsx

Document44.docx

Recommended textbooks for you

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

Principles of Information Systems (MindTap Course...

Computer Science

ISBN:9781285867168

Author:Ralph Stair, George Reynolds

Publisher:Cengage Learning

Microsoft Visual C#

Computer Science

ISBN:9781337102100

Author:Joyce, Farrell.

Publisher:Cengage Learning,

EBK JAVA PROGRAMMING

Computer Science

ISBN:9781337671385

Author:FARRELL

Publisher:CENGAGE LEARNING - CONSIGNMENT

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Principles of Information Systems (MindTap Course...
Computer Science
ISBN:9781285867168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning
Microsoft Visual C#
Computer Science
ISBN:9781337102100
Author:Joyce, Farrell.
Publisher:Cengage Learning,
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT