Consider languages over terminal alphabet 2 = {a,b,c,d}. • Give context-free grammars that generate the following five languages. • In each case, also give a derivation of the specified terminal string using your gram- mar. The derivation beginning from the start variable should indicate each individual derivation step using the notation ⇒. [a) L₁ = {b²i³k+1| k≥ i ≥ 0} Derivation for the string: 6²c4. b) L2 = { a¹b³c²i | i ≥ 1, k ≥ 1} U {c³k dk | k ≥ 1} Derivation for the string: a²bc². (c) L3 = {a²if²i+1¿5k+2 | i ≥ 1, k ≥ 1} {a²f³i+1³+¹d²+¹ | i ≥ 1, r d) L4 = a¹b¹c²d² Derivation for the string: a¹b³c². ≥ 1, s ≥ 1} Derivation for the string:

Consider languages over terminal alphabet 2 = {a,b,c,d}. • Give context-free grammars that generate the following five languages. • In each case, also give a derivation of the specified terminal string using your gram- mar. The derivation beginning from the start variable should indicate each individual derivation step using the notation ⇒. [a) L₁ = {b²i³k+1| k≥ i ≥ 0} Derivation for the string: 6²c4. b) L2 = { a¹b³c²i | i ≥ 1, k ≥ 1} U {c³k dk | k ≥ 1} Derivation for the string: a²bc². (c) L3 = {a²if²i+1¿5k+2 | i ≥ 1, k ≥ 1} {a²f³i+1³+¹d²+¹ | i ≥ 1, r d) L4 = a¹b¹c²d² Derivation for the string: a¹b³c². ≥ 1, s ≥ 1} Derivation for the string:

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

Grammar and its application to FractalsLet G=(N,T,P,∑) where ∑ is the start symbol, N = {D}, T = {d, r, l}, andP = {∑→D, D→DrDllDrD, D → d} 1. Give the most specific type of grammar G.2. Show the leftmost derivation sequence of the string drdlldrd, (i.e. When deriving a new sentential form, always replace one Nonterminal at a time and always replace the leftmost Nonterminal)3. Suppose d is an abstraction of a command to draw a straight line of fixed length in the current direction, r is an abstraction of a command to turn right by 60 degrees, and l is an abstraction of a command to turn left by 60 degrees. Assuming that you are to start from a point and that the starting direction is to proceed horizontally to the right, show the figure represented by the generated string drdlldrd.4. The string drdlldrdrdrdlldrdlldrdlldrdrdrdlldrd can also be generated. Assuming that you are to start from a point and that the starting direction is to proceed horizontally to the right, show the figure…
Design a context-free grammar for an alphabet, E = {a,b,c,d} that generates the language, L={a*b°c"d" | n 21, m 21} u {a"b"c"d°|n 21, m 21} Show that the grammar you designed is ambiguous by giving two different parse trees for some string in the language.
refer to the grammar S -> aSa | aXa X ->aXa | bYb Y -> bYb | empty where S is the start symbol, non-terminals = {S, X, Y}, terminals = {a, b} This Question: Use the pumping lemma to show that the language generated by this grammar is not regular.
Provide a (CFG) context-free grammar that generates the following language of all strings over alphabet {0,1} with twice as many 0's as l's. i.e: strings 001010, 110000, 010, 100, 010001 are in this language, while strings 0110, 1, 0, 0000000001 are not. Prove that your grammar is correct.
Consider a context-free grammar G = ({0, 1}, {S, A, B}, S, P), where P is the set of productions: SAB S → - - OA | 1B | E 1S | OAA OS | 1BB a) Give a leftmost derivation of the string 0011. b) Give a rightmost derivation of the string 0011. c) Draw a parse tree for the string 1001. d) Can the string 1110 be derived from the grammar G? If yes, write down the associated derivation tree. If not, give a justification.
1. Prove that the language L(G) is not regular where G is the following context-free grammar: G = ({S,A,B,C}, {a,b}, {S->bB|C, A>b|C, B->Sb, C->aAa }, S). Note: You must first determine L(G).
Convert the following Grammar to Chomsky normal form, upload a docx of your solution: S → aS | Sb | bT | U T → Ta | cUc | V | null U → aUa | S | null V → dV | d Please only provide the normal form :
Context-free grammars are sometimes used to model natural languages. In this problem you will model a fragment of the English language using context-free grammars. Consider the following English sentences: The girl is pretty. The girl that the boy likes is pretty. The girl that the boy that the clerk pushed likes is pretty. The girl that the boy that the clerk that the girl knows pushed likes is pretty. This is a special type of sentence built from a subject (The girl), a relative pronoun (that) followed by another sentence, a verb (is) and an adjective (pretty). Give a context-free grammar G that models this special type of sentence. Your terminals should be words or sequences of words like pretty or the girl. Is the language of G regular? If so, write a regular expression for it. If not, prove using the pumping lemma for regular languages. Can you give an example of a sentence that is in G but does not make sense in common English?
Given the following EBNF grammar: A -> [B, C,] D B-> '(, E, F, '), E C-> ', G D->-, G E -> " " F-> "o", "D", G-> "I" Give an example sentence that is within the grammar. NB: you can ignore whitespace.
Consider the following syntax-directed translation scheme. E-E + T{ print "+"; } | E+0|T T T.F(print ""; }|T.e|F F (E) | a { print "a"; } Note that e is an actual symbol, not an empty string. Assuming this grammar is implemented using an LR parser, what is the translation of (a+to).e? O Since the grammar is ambiguous, there is no one translation.
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
NAT Lang processing: Please explain in detail Consider a CFG representing a phrase structure grammar for a natural language such as English, including the following rule (the period is part of the rule): S -> NP VP . In this rule, S, NP, and VP are non-terminal symbols, but we will assume that the period is a terminal symbol specifically representing a period (as opposed to some other end-of-sentence marker). So, we can interpret this rule as stating that a sentence can have the form of a noun phrase followed by a verb phrase followed by a period. (To implement a parser for grammars with rules like this, the tokenizer would have to treat periods as separate tokens.) Assume that you need to convert this grammar to Chomsky normal form (CNF), perhaps with the CKY parsing algorithm in mind. Using the procedure discussed in class, show the rules that might result from the conversion.