Question

Give a context-free grammar for the following language. You must specify what language is generated by...

Give a context-free grammar for the following language. You must specify what language is generated by each non-terminal and briefly explain why.

Binary strings that have a remainder of 2 when divided by 5 (e.g., 111, 10, 10001).

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

As we know, mod N problems requires N number of states sn DFA. Here, 0 is the starting state and 2 is ending state. We kept 2 as final state because we need remainder as 2. Now, the interesting part about this DFA is that it can be converted to solve following problems also :-

N mod 5 = 0 if 0 is final state

N mod 5 = 1 if 1 is final state

N mod 5 = 2 if 2 is final state

N mod 5 = 3 if 3 is final state

N mod 5 = 4 if 4 is final state

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Please make a Context Free Grammar (CFG) for the regular languages below: The language that is...
Please make a Context Free Grammar (CFG) for the regular languages below: The language that is in C++ and containing lowercase and upper case letters, and also can have digits, and can also contain the underscore character '_', and it must begin with an underscore or a letter.
Give a right-linear grammar to generate each of the following: (a) All identifiers of lowercase letters...
Give a right-linear grammar to generate each of the following: (a) All identifiers of lowercase letters that either begin or end in a (or both). (b) The set of all integers and real numbers in decimal notation. No leading zeros should be generated and real numbers must have at least one digit on both sides of the decimal point. For instance, 3, +3, -3, 0, +0, -0, 0.00328, -100.46, and +100.000 are in the language, but 100., +, -, 003...
FOR MGMT 205 * I DO NOT WANT AN ANSWER THAT TALKS ABOUT TOBACCO OR BONDS**...
FOR MGMT 205 * I DO NOT WANT AN ANSWER THAT TALKS ABOUT TOBACCO OR BONDS** Your problem will have exactly two variables (an X1 and an X2) and will incorporate a maximization (either profit or revenue) objective. You will include at least four constraints (not including the X1 ? 0 and X2 ? 0 [i.e., the “Non-negativity” or “Duh!”] constraints). At least one of these four must be a “?” constraint, and at least one other must be a...
To complete each assignment, you will need to read the case study. Assume that the client...
To complete each assignment, you will need to read the case study. Assume that the client described in each case study meets criteria for a DSM-5 disorder. You will then consult the DSM-5 criteria and write 1-2 detailed paragraphs in which you assign a primary diagnosis for the client and justify that diagnosis. In this section you should reference EACH of the DSM-5 criteria for the diagnosis you are assigning and provide evidence from the case study for or against...
Have you ever wondered what it means to click the “offset carbon emissions” button when you...
Have you ever wondered what it means to click the “offset carbon emissions” button when you book a flight or train trip? It adds a small cost to your ticket, but how does this reduce emissions? The money is typically used to fund projects that reduce carbon emissions. One such project type is the introduction of more efficient cooking stoves into communities. Much of the world uses inefficient charcoal or wood stoves that result in excessive indoor air pollution, deforestation,...
comment on 2 things you learned from this chapter of the Cognitive development ece 124 chapter...
comment on 2 things you learned from this chapter of the Cognitive development ece 124 chapter 9 Piaget -Preoperational intelligence • Cognitive development between the ages of about 2 and 6 • Includes language and imagination • Suggests logical, operational thinking is not yet possible at this stage Piaget: Symbolic Thought • Major accomplishment of preoperational intelligence • Allows a child to think symbolically, including understanding that words can refer to things not seen and that an item can symbolize...
Procedure I. Reverse Transcription. For each of your RNA samples set up the following reaction: *Remember...
Procedure I. Reverse Transcription. For each of your RNA samples set up the following reaction: *Remember to use proper RNA handling technique! 1. In a 0.2 ml size RNAse-Free tube add the following: • 0.5 µg RNA (no more than 6 µl) You can add as little as 0.1 µg of RNA if your concentration is low • 2 µl dT primer • Nuclease Free Water to final volume of 8 µl * Before you start write the exact volume...
#########################PANDAS LANGUAGE################## #########################MATPLOT LIB######################### # filter the movies with specific actor's name ​# List of top...
#########################PANDAS LANGUAGE################## #########################MATPLOT LIB######################### # filter the movies with specific actor's name ​# List of top 5 Actor per year who has highest rating from the year 2010 - 2017 ​# plot horizontal barcahrt of upper output # visualize those to 10 runtime of movies ​# visualize those to 10 runtime which has highest rating of movies ​# show count all movies which has rating more 3.0 and less than 7.0​ # plot vertical barchart of upper output, movies w.r.t...
To complete each assignment, you will need to read the case study. Assume that the client...
To complete each assignment, you will need to read the case study. Assume that the client described in each case study meets criteria for a DSM-5 disorder. You will then consult the DSM-5 criteria and write 1-2 detailed paragraphs in which you assign a primary diagnosis for the client and justify that diagnosis. In this section you should reference EACH of the DSM-5 criteria for the diagnosis you are assigning and provide evidence from the case study for or against...
A new family has just been referred to your program. Before you meet, you review what...
A new family has just been referred to your program. Before you meet, you review what you know about the family. Soha arrived 10 months ago with her children, sponsored by other family members. Her husband has found work in another city, but Soha and the children are living with their relatives and usually see the father only on weekends. They are a visible minority in a predominantly white neighborhood. Soha and the children have a room in the basement....
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT