(a) Construct deterministic finite automata (in the form of diagrams) accepting the following languages: 1. (i) {w e {0,1}* | w has neither 00 nor 111 as a subword} (ii) {w e {0,1}* | w has an odd number of 0's or an even number of 1's} (pay attention to connective or in this definition) (iii) {w e {0, 1}° | the length of w is either even or divisible by 3} (iv) {w e {0, 1}* | w = 01ul0 for some word u e {0,1}*} (b) Construct nondeterministic finite automata (in the form of diagrams) accepting the anguages in {a, b}* represented by the following regular expressions: (i) (a Ub)*abba(a Ub)* (ii) ((aa) bb U ab)* (c) Is it possible to write a regular expression representing the following language? {02n13n e {0, 1}* |n = 1, 2,...} If yes, then write such a regular expression, else prove that this is impossible. (d) For the same language as in (c), (02" 13n e {0, 1}* | n = 1, 2,...} is it possible to write a context-free grammar representing it? If yes, then write such a grammar, else prove that this is impossible.
(a) Construct deterministic finite automata (in the form of diagrams) accepting the following languages: 1. (i) {w e {0,1}* | w has neither 00 nor 111 as a subword} (ii) {w e {0,1}* | w has an odd number of 0's or an even number of 1's} (pay attention to connective or in this definition) (iii) {w e {0, 1}° | the length of w is either even or divisible by 3} (iv) {w e {0, 1}* | w = 01ul0 for some word u e {0,1}*} (b) Construct nondeterministic finite automata (in the form of diagrams) accepting the anguages in {a, b}* represented by the following regular expressions: (i) (a Ub)*abba(a Ub)* (ii) ((aa) bb U ab)* (c) Is it possible to write a regular expression representing the following language? {02n13n e {0, 1}* |n = 1, 2,...} If yes, then write such a regular expression, else prove that this is impossible. (d) For the same language as in (c), (02" 13n e {0, 1}* | n = 1, 2,...} is it possible to write a context-free grammar representing it? If yes, then write such a grammar, else prove that this is impossible.
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Transcribed Image Text:(a) Construct deterministic finite automata (in the form of diagrams) accepting the
following languages:
1.
(i)
{w e {0,1}* | w has neither 00 nor 111 as a subword}
(ii) {w e {0,1}* | w has an odd number of 0's or an even number of l's}
(pay attention to connective or in this definition)
(iii) {w e {0, 1}° | the length of w is either even or divisible by 3}
(iv) {w e {0, 1}* | w = 01ul0 for some word u e {0,1}*}
(b) Construct nondeterministic finite automata (in the form of diagrams) accepting the
anguages in {a, b}* represented by the following regular expressions:
(i) (a Ub)*abba(a Ub)*
(ii) ((aa)*bb U ab)*
(c) Is it possible to write a regular expression representing the following language?
{02n13n e {0, 1}* |n = 1, 2,...}
If yes, then write such a regular expression, else prove that this is impossible.
(d) For the same language as in (c),
(02" 1 3n e {0, 1}* | n = 1, 2,...}
is it possible to write a context-free grammar representing it? If yes, then write such
a grammar, else prove that this is impossible.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps with 2 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY