Homework Help is Here – Start Your Trial Now!
Engineering
Computer Engineering
Prof. has installed a meme vending machine a machine that will accept coins and dispense a meme - in the class. It accepts any amount of money in pennies (p), nickels (n), and dimes (d) as long as the coins are deposited in non-decreasing order of values. For example, a meme will be dispensed by the machine if the user deposits coins in the order described by the following strings: ppp, n, nd, pnd, pppnndd, d. A meme would not be dispensed by the machine if the user deposits coins in the order described by the following strings: ndp, dp, pnp, ddnn. Consider the alphabet of pennies, nickels, and dimes as E₂ = {p, n, d} where p denotes a Σ2 penny, n denotes a nickel, and d denotes a dime. Let L2 be the language over Σ2 such that L₂= {w coins deposited in the order described in w would dispense a meme.} Therefore, the strings ppp, n, nd, pnd, pppnndd, d are in L2 and strings ndp, dp, pnp, ddnn are not in L₂. 1. Give a regular expression that describes all the strings in the language L₂. 2. Give a regular expressions that describes all the strings not in L₂. 3. Design a DFA or NFA that recognizes the langauge L2.

Prof. has installed a meme vending machine a machine that will accept coins and dispense a meme - in the class. It accepts any amount of money in pennies (p), nickels (n), and dimes (d) as long as the coins are deposited in non-decreasing order of values. For example, a meme will be dispensed by the machine if the user deposits coins in the order described by the following strings: ppp, n, nd, pnd, pppnndd, d. A meme would not be dispensed by the machine if the user deposits coins in the order described by the following strings: ndp, dp, pnp, ddnn. Consider the alphabet of pennies, nickels, and dimes as E₂ = {p, n, d} where p denotes a Σ2 penny, n denotes a nickel, and d denotes a dime. Let L2 be the language over Σ2 such that L₂= {w coins deposited in the order described in w would dispense a meme.} Therefore, the strings ppp, n, nd, pnd, pppnndd, d are in L2 and strings ndp, dp, pnp, ddnn are not in L₂. 1. Give a regular expression that describes all the strings in the language L₂. 2. Give a regular expressions that describes all the strings not in L₂. 3. Design a DFA or NFA that recognizes the langauge L2.

Computer Networking: A Top-Down Approach (7th Edition)
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...
See similar textbooks
icon
Related questions
Question
100%
4. Any DFA that recognizes L₂ should have at least 4 states. Provide 4 strings w₁, W2, W3, and w₁ that will necessarily end up in different states in any DFA that accepts L2. (i) w₁ = (ii) W₂ = (iii) W3 = (iv) W₁ = 5. For each of the pairs (w₁, W₂), (w₁, W3), (W₁, W₁), (W2, W3), (W2, W₁), (W3, W₁), arrive at a contradiction if any pair of strings go to the same state.
Transcribed Image Text:4. Any DFA that recognizes L₂ should have at least 4 states. Provide 4 strings w₁, W2, W3, and w₁ that will necessarily end up in different states in any DFA that accepts L2. (i) w₁ = (ii) W₂ = (iii) W3 = (iv) W₁ = 5. For each of the pairs (w₁, W₂), (w₁, W3), (W₁, W₁), (W2, W3), (W2, W₁), (W3, W₁), arrive at a contradiction if any pair of strings go to the same state.
Prof. has installed a meme vending machine a machine that will accept coins and dispense a meme - in the class. It accepts any amount of money in pennies (p), nickels (n), and dimes (d) as long as the coins are deposited in non-decreasing order of values. For example, a meme will be dispensed by the machine if the user deposits coins in the order described by the following strings: ppp, n, nd, pnd, pppnndd, d. A meme would not be dispensed by the machine if the user deposits coins in the order described by the following strings: ndp, dp, pnp, ddnn. Consider the alphabet of pennies, nickels, and dimes as Σ₂ = {p, n, d} where p denotes a penny, n denotes a nickel, and d denotes a dime. Let L₂ be the language over E₂ such that L₂ = {w | coins deposited in the order described in w would dispense a meme.} Therefore, the strings ppp, n, nd, pnd, pppnndd, d are in L2 and strings ndp, dp, pnp, ddnn are not in L2. 1. Give a regular expression that describes all the strings in the language L₂. 2. Give a regular expressions that describes all the strings not in L2. 3. Design a DFA or NFA that recognizes the langauge L2.
Transcribed Image Text:Prof. has installed a meme vending machine a machine that will accept coins and dispense a meme - in the class. It accepts any amount of money in pennies (p), nickels (n), and dimes (d) as long as the coins are deposited in non-decreasing order of values. For example, a meme will be dispensed by the machine if the user deposits coins in the order described by the following strings: ppp, n, nd, pnd, pppnndd, d. A meme would not be dispensed by the machine if the user deposits coins in the order described by the following strings: ndp, dp, pnp, ddnn. Consider the alphabet of pennies, nickels, and dimes as Σ₂ = {p, n, d} where p denotes a penny, n denotes a nickel, and d denotes a dime. Let L₂ be the language over E₂ such that L₂ = {w | coins deposited in the order described in w would dispense a meme.} Therefore, the strings ppp, n, nd, pnd, pppnndd, d are in L2 and strings ndp, dp, pnp, ddnn are not in L2. 1. Give a regular expression that describes all the strings in the language L₂. 2. Give a regular expressions that describes all the strings not in L2. 3. Design a DFA or NFA that recognizes the langauge L2.
Expert Solution
Step 1

We need to find regular expression and DFA for the given language.

***As per the guidelines only 1st 3 questions are answered. For other questions please post separate queries.

steps

Step by step

Solved in 2 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
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 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)
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
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY
SEE MORE TEXTBOOKS