Design a non-ambiguous grammar generating the language consisting of all binary strings, which contain an odd...
Design a non-ambiguous grammar generating the language consisting of all binary strings, which contain an odd number of 0’s and an odd number of 1’s. Justify correctness of your construction.
Homework Answers
Answer :
C → 0B | 1A
P → 0A | 1B | ε
A → 0P | 1C
B → 1P | 0C
Explanation :
Example string to parse the grammar : 010101
C -> 0B
-> 01P
-> 010A
-> 0101C
-> 01010B
-> 010101P
-> 010101
Add Answer to:
Design a non-ambiguous grammar generating the language
consisting of all binary strings, which contain an odd...
Design an attribute grammar recognizing the language consisting of binary strings containing the same number of...
Design an attribute grammar recognizing the language consisting of binary strings containing the same number of 0’s and 1’s. Explain your construction
Write a context-free grammar for the language where all strings are of even length and the...
Write a context-free grammar for the language where all strings are of even length and the first half of the string is all 0’s, but it must be an odd number of 0’s
1. Let £ = {0,1} and consider the language L of all binary strings of odd...
1. Let £ = {0,1} and consider the language L of all binary strings of odd length with a 0 in the middle. Give a Turing machine that decide L.
13.) Write a grammar for the language consisting of strings that have n copies of the...
13.) Write a grammar for the language consisting of strings that have n copies of the letter a followed by one more number of copies of the letter b, where n>0. For example, the strings abb, aaaabbbbb, and aaaaaaaabbbbbbbbb are in the language but a, ab, ba, and aaabb are not. Answer the aaaaaabbbbbbbh are in the languagebr 14.) Draw parse trees for the sentences abb and aabbb, as derived from the grammar of Problem 13. Answer:
For each of the following, construct context-free grammars that generate the given set of strings. If...
For each of the following, construct context-free grammars that generate the given set of strings. If your grammar has more than one variable, we will ask you to write a sentence describing what sets of strings you expect each variable in your grammar to generate. For example, if your grammar were: S → EO E → EE CC 0+ EC C+01 We would expect you to say “E generates (non-empty) even length binary strings; O generates odd length binary strings;...
Express as a set using set-builder notation The set of all binary strings that contain at...
Express as a set using set-builder notation The set of all binary strings that contain at least one 0 and at least one 1. The set of all binary strings with even length. The set of all binary strings that contain an even number of 1’s. The set of all binary strings that read the same forward and backwards
Draw an automaton which will accept all integers (in binary form) of Odd parity (number of...
Draw an automaton which will accept all integers (in binary form) of Odd parity (number of 1’s in the string is odd). Now write a code in a high level language (C++) for the automaton. Take inputs of two strings, one of odd parity (e.g, 00111011) and another one of even parity (e.g., 1100110011). Your code should accept the right string and reject the wrong one. Print your code and results
If you could please help with 1-3. 4 if you can but it is not necessary....
If you could please help with 1-3. 4 if you can but it is not
necessary. Thanks
Name: Solve problems 1-3. Problem 4 counts for extra credit. Each problem counts for 3 points. 1. Construct a non-ambiguous grammar generating the language consisting of all strings over the alphabet = {0,1,2), which contain no adjacent 1's. Provide a justification of correctness of your construction. 2. A Huffman tree constructed out of characters aj, az, az, ..., an, occurring with frequencies fi...
Design a regular grammar to generate the set of all even integers. Design a regular grammar...
Design a regular grammar to generate the set of all even integers. Design a regular grammar to generate the set of all odd integers. Design a regular grammar to generate the set of all integers beginning with the digit 8 such that the digits are consecutive and even. If a digit is 8, its following digit (if present) will be 0. The set of valid strings is {8, 80, 802,8024, 80246, 802468,...) Design a regular grammar to generate the set...
can you plzz do question 1 and 2 Question 1. Design a CFG for the language...
can you plzz do question 1 and 2
Question 1. Design a CFG for the language over = {1, #} whose elements consist of every pair of distinct, #-separated unary values: L = {rı#x2 | 21, 22 € 1", 21 * x2}. Question 2. Design a CFG for the language of binary strings that contain at least one 1 in their second half: L = {uv | UE (OU 1)", v € OU 1)*1(0U 1)", [u '}. Question 3. This...
1. Let £ = {0,1} and consider the language L of all binary strings of odd length with a 0 in the middle. Give a Turing machine that decide L.
13.) Write a grammar for the language consisting of strings that have n copies of the letter a followed by one more number of copies of the letter b, where n>0. For example, the strings abb, aaaabbbbb, and aaaaaaaabbbbbbbbb are in the language but a, ab, ba, and aaabb are not. Answer the aaaaaabbbbbbbh are in the languagebr 14.) Draw parse trees for the sentences abb and aabbb, as derived from the grammar of Problem 13. Answer:
For each of the following, construct context-free grammars that generate the given set of strings. If your grammar has more than one variable, we will ask you to write a sentence describing what sets of strings you expect each variable in your grammar to generate. For example, if your grammar were: S → EO E → EE CC 0+ EC C+01 We would expect you to say “E generates (non-empty) even length binary strings; O generates odd length binary strings;...
If you could please help with 1-3. 4 if you can but it is not
necessary. Thanks
Name: Solve problems 1-3. Problem 4 counts for extra credit. Each problem counts for 3 points. 1. Construct a non-ambiguous grammar generating the language consisting of all strings over the alphabet = {0,1,2), which contain no adjacent 1's. Provide a justification of correctness of your construction. 2. A Huffman tree constructed out of characters aj, az, az, ..., an, occurring with frequencies fi...
Design a regular grammar to generate the set of all even integers. Design a regular grammar to generate the set of all odd integers. Design a regular grammar to generate the set of all integers beginning with the digit 8 such that the digits are consecutive and even. If a digit is 8, its following digit (if present) will be 0. The set of valid strings is {8, 80, 802,8024, 80246, 802468,...) Design a regular grammar to generate the set...
can you plzz do question 1 and 2
Question 1. Design a CFG for the language over = {1, #} whose elements consist of every pair of distinct, #-separated unary values: L = {rı#x2 | 21, 22 € 1", 21 * x2}. Question 2. Design a CFG for the language of binary strings that contain at least one 1 in their second half: L = {uv | UE (OU 1)", v € OU 1)*1(0U 1)", [u '}. Question 3. This...
Most questions answered within 3 hours.
-
The extent to which assets are financed by borrowed funds and
other liabilities is indicated by:...
asked 32 minutes ago -
Explain in detail
Germany is the fifth largest economy
explain what goods and services Germany specializes...
asked 47 minutes ago -
The density of platinum is 21.45 g/mL. If a cube of platinum
with a mass of...
asked 52 minutes ago -
Accounts Receivable
Sales
A/R Posting
Extended Sales Invoice
Packing Slip
Compare invoice to packing slip 2...
asked 55 minutes ago -
Michaella, age 23, is a full-time law student and is claimed by
her parents as a...
asked 56 minutes ago -
Why are polymers not typically casted into products?
asked 1 hour ago -
When rolling a die 129 times, what is the probability of rolling
a 6 no more...
asked 1 hour ago -
4. A call option currently sells for $7.75. It has a strike
price of $85 and...
asked 1 hour ago -
1.
You need to prepare 10.0 liters of an acid aqueous solution with a
pH of...
asked 1 hour ago -
Along an aggregate supply curve, if the level of output is less
than the natural level...
asked 1 hour ago -
By 2025, annual consumption in emerging markets will total $30
trillion and contribute more than ________...
asked 1 hour ago -
At what point does reformation cease to be a viable option for
those who are oppressed...
asked 1 hour ago