Consider a context-free grammar G with the following productions, S → ASA | B В — аСЬ | ЬСа C'→ ACA | A A → a|b and answer the following questions: (a) What are the variables and terminals of G? (b) Give three strings of length 7 in L(G). (c) Are the following strings in L(G)? (i) аа (ii) bbb (iii) aba (iv) abb (d) True or false: C = bab (e) True or false: C → bab (f) True or false: C abab (g) True or false: C → AAA (h) Is A in L(G)?

Consider a context-free grammar G with the following productions, S → ASA | B В — аСЬ | ЬСа C'→ ACA | A A → a|b and answer the following questions: (a) What are the variables and terminals of G? (b) Give three strings of length 7 in L(G). (c) Are the following strings in L(G)? (i) аа (ii) bbb (iii) aba (iv) abb (d) True or false: C = bab (e) True or false: C → bab (f) True or false: C abab (g) True or false: C → AAA (h) Is A in L(G)?

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

2. If L is a regular language over E, what can be said about the languages L1 = E* – L and L2 = reverse(L*)? A. Li is always regular but not L2. B. L2 is always regular but not L1. C. Li and L2 are both regular. 3. What is the language generated by the grammar G: { S → aR , R → aR| baR|b }? A. (aa*b)* B. (a*b)(a*b)* C. (aa*b)(aa*b)* 4. IfL is a regular language over some alphabet E, what can be said about the language L’ = (E* – L) N reverse(L)? A. L' is surely regular. B. L’ is surely non-regular. C. Its type cannot be determined without additional information. 5. Including the trap state, how many states are there in the minimum-state DFA for the regular expression (a+b)*(b+c)* ? Also how many final states will there be in the minimum-state DFA? A. 4 states with one final state B. 3 states with two final states C. 3 states with one final state
1. Use the algorithm described in class that takes a CFG and converts it into a CNF (Chomsky Normal Form) grammar that generates the same language as the original grammar, except possibly for the string A, to answer the following question. As part of your answer, you should say which variables are nullable, and you should give the appropriate grammar after each step of the algorithm. There are four steps. Give a CFG (context-free grammar) in CNF (Chomsky Normal Form) that generates the same language, except possibly for the string A, as the following grammar: SAB AB →bAa A → aaB bb
Let G = (V. E. P, S) be a context-free grammar in which S only when n = 0. G is an LR(k) grammar (k ≥ 0) if (i) SaAw⇒ aßw, where a, ß € V*, we Σ*, R R (ii) Sα'A'w'α'B'w', where o', ß' = V*, w' e Σ*, and R (iii) the first aß + k symbols of aßw and a'B'w' coincide. Then α = α', A = A', B = B'.
This question is about context-free grammars and parsing, and Turing machines (TM’s). Question 1) Consider the following context-free grammar G over the alphabet Σ = {a, b, c}: S → aSb | ε | acSba | abc Using any of the grammar transformation techniques we saw in this module, construct a CNFgrammar that generates the same language as the grammar G of Question 1.Make sure you include in your answer all individual steps that you followed. Please help me with this question :)
What can be claimed about the grammar G: {S→ alaRb, R→ b|bSa }? OA. G is a context-free grammar and L(G) is a context-free language. B. G is a context-free grammar but L(G) is actually a regular language. O C. G is a regular grammar and L(G) is a regular language. What can be said about the grammar G: {S → ORO|OR1|1RO|1R1, R → E|OR|1R }? OA. G is a context-free grammar and L(G) is a context-free language. B. G is a context-free grammar but L(G) is the regular language (0+1)²(0+1)* C. G is a regular grammar and L(G) is the regular language (0+1)(0+1)*
Consider the following grammar G: S> XZ X> abXba |e |Y Y> cYd|cd z> abz| € a. True or False? If true, show the derivation of the string, using proper notation i. S=* abccddbaab ii. S=* abbacd iii. S=* cd iv. S=* € b. Describe L(G) using set notation, i.e., which types of strings are generated using G
Let ANTIPALINDROME be the language of all even-length strings over the alphabet {a,b} such that, for all i, the i-th letter from the start is different to the i-th letter from the end. Examples of strings in this language include: ε, ab, ba, aabb, abab, baba, bbaa, aaabbb, ... Give a Context-Free Grammar for the language ANTIPALINDROME.
You are given the following context-free grammar:S → EGF HE → eE | eF → f | EG → gH → hH | hh | eQUESTIONS:1. Convert the grammar into the Chomsky normal form(show all steps of the conversion).2. Use the CYK algorithm to check if the word egehh is inthe language of the grammar.
Consider the following grammar: → a b > b | b b Which of the following sentences are in the language generated by this grammar? a. babb b. bbbabb c. bbaaaaabc d. aaaaaa
6. Find an s-grammar for L = {a2nb" :n 2 2}. 7. Convert the grammar S- assb | bSa |a | b| ab into Greibach normal form.
2. Answer each of the following questions for context-free grammar G. R→ XRX | S S→ aTb | bTa T→ XTX | X | ε X → a b a. What are the variables of G? b. What are the terminals of G? c. Which is the start variable of G? d. Give three strings in L(G). e. True or False: T⇒ aba. * f. True or False: T⇒ aba. g. True or False: T⇒ T. * h. True or False: T⇒ T. * i. True or False: XXX⇒ aba. * j. True or False: X⇒ aba. * k. True or False: T⇒ XX. * 1. True or False: T⇒ XXX. * m. True or False: S => ɛ.PLEASE ONLY ANSWER i-m
Computer Science Consider the context free grammar (CFG):S -> AB (S being the start symbol)A ->aAb | aabbB -> cBd | cdThe grammar is strong LL(k).a) Determine the value of k.b) As a result of a) above, compute the corresponding look ahead sets (for eachproduction).c) As a result of b) above, write (in C++ pseudo code) the corresponding recursivedescent parser (for the grammar)..