Consider the CFG, G, defined as: S - AB A - aA | a B - bB | b (S being the start symbol) a) Apply the push down automaton (PDA) algorithm to determine whether or not the well formed formula (wff): abb, is in the language (L) generated by G, L(G). b) Is G regular? If it is, write down the corresponding regular grammar. If it is not, explain in details why it is not.

Consider the CFG, G, defined as: S - AB A - aA | a B - bB | b (S being the start symbol) a) Apply the push down automaton (PDA) algorithm to determine whether or not the well formed formula (wff): abb, is in the language (L) generated by G, L(G). b) Is G regular? If it is, write down the corresponding regular grammar. If it is not, explain in details why it is not.

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

Let G = (V, E, R, S) be a grammar with V= {S, H, Gm J}; = {h, g. j}; and the set of rules: H>h | hJG G> Gg | Sg | HgJ J→ jH | HHJ| Jj Convert this grammar to a PDA using the method we described.
1. Consider the following context-free grammar with start symbol S, nonterminals {S, A, B, C}, and terminals {0,1}: SAO A→B A → C1 B→ 1 B→ E C→ 0 (a) Compute all the sets FIRST and FOLLOW necessary to implement a recursive decent parser for this grammar. However, do not list any unnecessary such a set. (b) Investigate all the combinations of sets FIRST and FOLLOW that are involved in the im- plementation of a recursive descent parser for this grammar. Explain how these com- bination make the grammar suitable or unsuitable (as the case might be) for recursive descent parsing.
1)Let G = (V, ∑, R, S) be a grammar with V = {S, H, Gm J}; ∑ = {h, g, j}; and the set of rules: S → H H → h | hJG G → Gg | Sg | HgJ J → jH | HHJ| Jj a)Convert this grammar to a PDA using the method we described. b)Convert G to Chomsky normal form.
Refer to image and provide correct solution for positive feedback Computation and Automata
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 context-free grammar defined by the tuple G and by the rules that appear in the image. a) Show that no string in L (G) contains "ba" as a substring. It is suggested to proceed by induction over the length of the chain. b) Informally describe L (G). Justify your answer using a). (Remember that the symbol | is disjunctive, and is used in this case to compactly represent four rules.)
Answer the given question with a proper explanation and step-by-step solution. Using the algorithm discussed in class, ”Big loop algorithm” show the transition diagram for a pushdown automaton (PDA) to recognize the language generated by G, which ahs the following grammer rules S →BAC A →a | b | c | ε B →bB | b C →cC | ε Fully define for the grammar G above, that is G = (....Describe in English what language the grammar G generates . Give an example showing that the grammar G above is ambiguous
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).
Subject : Theory of computing
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.
5
5 The production rules for a grammar G with start symbol S, terminals a, b, and c and non-terminals X, Y, and Z is given below: G: XY a |YZ 6| ZX e| XY Y a) Show that G generates bacab (i.e., that S bacab). b) Is Ga regular grammar? Explain. c) Is G a type 2 (context free) grammar? Explain. 6 Show that if A is a regular language, then the complement of A is also regular. (We can denote the complement of A as A= A° = {r|z¢ A}.)