Using the CYK algorithm, determine whether the word “abbaa” can be generated by the following grammar:...
Using the CYK algorithm, determine whether the word “abbaa” can be generated by the following grammar:
S ⟶ XY
X ⟶ SY
Y ⟶ SS
X ⟶ a | bb
Y ⟶ aa
What are all the producing nonterminals for the substring "bb"?
What are all the producing nonterminals for the substring "baa"?
What are all the producing nonterminals for the substring "abb"?
What are all the producing nonterminals for the substring "bbaa"?
Homework Answers
First of all the given grammar is not in CNF normal form. Since for CYK algorithm the CNF form of the grammar is required.
Here I have implement the CYK algorithm in Table filling Form. Here
Xi j contain all the non terminals which generate string ai ai+1 ai+2 .... aj.
means if X1n contains start symbol of the grammar then the string a1 a2 a3 .......an .
The full solution is attached
as image form. there is three images numbered as 1, 2, 3.
Add Answer to:
Using the CYK algorithm, determine whether the word “abbaa” can
be generated by the following grammar:...
theory of computation (10) Use the CYK algorithm to determine whether the strings abb, bbb, aabba,...
theory of computation
(10) Use the CYK algorithm to determine whether the strings abb, bbb, aabba, and abbbb are in the language generated by the grammar S - AB ABB a BAB 6
2. The following context-free grammar (CFG) has A-productions. S + XY | XYZ X + YXYZ...
2. The following context-free grammar (CFG) has A-productions. S + XY | XYZ X + YXYZ | a | A Y + XZ | ZY | 6 | A Z YZ | XY | X | C Using the algorithm in Chapter 13, find another CFG that generates the same language except for the empty word, and that does not have any A-productions.
5. Construct the CYK-table for the string aabb using the following grammar: S X Y Z...
5. Construct the CYK-table for the string aabb using the following grammar: S X Y Z A B + AY | 8 + AY + XZ|XB| b + XB | b → a + b
4. Consider the following context-free grammar S SSSS a (a) Show how the string aa+a* can...
4. Consider the following context-free grammar S SSSS a (a) Show how the string aa+a* can be generated by this grammar (b) What language does this grammar generate? Explain
(10] Eliminate left recursion from the grammar A Ba |Aa c B Bb | Ab 1...
(10] Eliminate left recursion from the grammar A Ba |Aa c B Bb | Ab 1 d A Ad IB A BA ASJAE Consider the following grammar G: S'S S (S)S|e fa) (10] Construct the collection of the sets of LR(0) items (b) [5] When constructing the action table of SLR parser of G what are the rules to determine the parsing actions? That is, what is the rule for a shift action at state /? What is the rule...
3 points) Question Three Consider the context-free grammar S >SS+1 SS 1a and the string aa...
3 points) Question Three Consider the context-free grammar S >SS+1 SS 1a and the string aa Give a leftmost derivation for the string. 3 points) (4 poiots) (5 points) (3 points) sECTION IWOLAttcmpt.any 3.(or 2) questions from this.scction Suppose we have two tokens: (1) the keyword if, and (2) id-entifiers, which are strings of letters other than if. Show the DFA for these tokens. Give a nightmost derivation for the string. Give a parse tree for the string i) Is...
(b) Using the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, determine whether the following formula is satisfiable. Show each step. [3 marks] (c) Give an example of a conjunctive normal form (...
(b) Using the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, determine whether the following formula is satisfiable. Show each step. [3 marks] (c) Give an example of a conjunctive normal form (CNF) formula where the pure literal rule can be applied, but the unit propagation rule cannot. The formula must have at least 3 clauses. [3 marks
(b) Using the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, determine whether the following formula is satisfiable. Show each step. [3 marks] (c) Give an example of a conjunctive normal form...
Directions. Determine whether the following three arguments are valid using the truth table method. Use the...
Directions. Determine whether the following three arguments are valid using the truth table method. Use the Indirect Truth Table method as found in the link on Canvas. Indicate whether each is valid or not. Note that ‘//’ is used as the conclusion indicator and ‘/’ is used to separate the premises. [Note: Use only the following logical symbols: ‘&’ for conjunctions, ‘v’ for disjunctions, ‘->’ for conditionals, ‘<->’ for biconditionals, ‘~’ for negations.] Show your truth tables. 1. (S <->...
11 Write a function with the following prototype: /* Determine whether arguments can be added without overflow */ int u...
11 Write a function with the following prototype: /* Determine whether arguments can be added without overflow */ int uadd_ok (unsigned x, unsigned y); This function should return 1 if arguments x and y can be added without causing overflow
11 Write a function with the following prototype: /* Determine whether arguments can be added without overflow */ int uadd_ok (unsigned x, unsigned y); This function should return 1 if arguments x and y can be added without causing overflow
Tired of collecting data at night, you decide to switch to a project studying whether pesticide-resistance...
Tired of collecting data at night, you decide to switch to a project studying whether pesticide-resistance genes from GMO crops are being spread among neighboring farms by pollinators. On Farm X, all of the corn plants are heterozygous at the pesticide resistant gene (genotype Aa). The "A" allele is dominant and confers resistance to pesticide. All of the corn plants planted on Farm Yare homozygous for aa (i.e. they have no copies of the A allele). If you know that...
theory of computation
(10) Use the CYK algorithm to determine whether the strings abb, bbb, aabba, and abbbb are in the language generated by the grammar S - AB ABB a BAB 6
2. The following context-free grammar (CFG) has A-productions. S + XY | XYZ X + YXYZ | a | A Y + XZ | ZY | 6 | A Z YZ | XY | X | C Using the algorithm in Chapter 13, find another CFG that generates the same language except for the empty word, and that does not have any A-productions.
5. Construct the CYK-table for the string aabb using the following grammar: S X Y Z A B + AY | 8 + AY + XZ|XB| b + XB | b → a + b
4. Consider the following context-free grammar S SSSS a (a) Show how the string aa+a* can be generated by this grammar (b) What language does this grammar generate? Explain
(10] Eliminate left recursion from the grammar A Ba |Aa c B Bb | Ab 1 d A Ad IB A BA ASJAE Consider the following grammar G: S'S S (S)S|e fa) (10] Construct the collection of the sets of LR(0) items (b) [5] When constructing the action table of SLR parser of G what are the rules to determine the parsing actions? That is, what is the rule for a shift action at state /? What is the rule...
3 points) Question Three Consider the context-free grammar S >SS+1 SS 1a and the string aa Give a leftmost derivation for the string. 3 points) (4 poiots) (5 points) (3 points) sECTION IWOLAttcmpt.any 3.(or 2) questions from this.scction Suppose we have two tokens: (1) the keyword if, and (2) id-entifiers, which are strings of letters other than if. Show the DFA for these tokens. Give a nightmost derivation for the string. Give a parse tree for the string i) Is...
(b) Using the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, determine whether the following formula is satisfiable. Show each step. [3 marks] (c) Give an example of a conjunctive normal form (CNF) formula where the pure literal rule can be applied, but the unit propagation rule cannot. The formula must have at least 3 clauses. [3 marks
(b) Using the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, determine whether the following formula is satisfiable. Show each step. [3 marks] (c) Give an example of a conjunctive normal form...
11 Write a function with the following prototype: /* Determine whether arguments can be added without overflow */ int uadd_ok (unsigned x, unsigned y); This function should return 1 if arguments x and y can be added without causing overflow
11 Write a function with the following prototype: /* Determine whether arguments can be added without overflow */ int uadd_ok (unsigned x, unsigned y); This function should return 1 if arguments x and y can be added without causing overflow
Tired of collecting data at night, you decide to switch to a project studying whether pesticide-resistance genes from GMO crops are being spread among neighboring farms by pollinators. On Farm X, all of the corn plants are heterozygous at the pesticide resistant gene (genotype Aa). The "A" allele is dominant and confers resistance to pesticide. All of the corn plants planted on Farm Yare homozygous for aa (i.e. they have no copies of the A allele). If you know that...
Most questions answered within 3 hours.
-
The density of platinum is 21.45 g/mL. If a cube of platinum
with a mass of...
asked 52 seconds from now -
Accounts Receivable
Sales
A/R Posting
Extended Sales Invoice
Packing Slip
Compare invoice to packing slip 2...
asked 2 minutes ago -
Michaella, age 23, is a full-time law student and is claimed by
her parents as a...
asked 2 minutes ago -
Why are polymers not typically casted into products?
asked 19 minutes ago -
When rolling a die 129 times, what is the probability of rolling
a 6 no more...
asked 36 minutes ago -
4. A call option currently sells for $7.75. It has a strike
price of $85 and...
asked 25 minutes ago -
1.
You need to prepare 10.0 liters of an acid aqueous solution with a
pH of...
asked 28 minutes ago -
Along an aggregate supply curve, if the level of output is less
than the natural level...
asked 28 minutes ago -
By 2025, annual consumption in emerging markets will total $30
trillion and contribute more than ________...
asked 33 minutes ago -
At what point does reformation cease to be a viable option for
those who are oppressed...
asked 37 minutes ago -
Place letters corresponding to amounts in the proper order for
lightest to heaviest samples:
a) 2100...
asked 41 minutes ago -
Consider the multicore processor with 6 heterogeneous cores
labelled C1, C2, C3, C4, C5, and C6....
asked 44 minutes ago