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

I need help in these question relating to Context Free Grammar
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…
THEORY of Automata. grammar G
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).
Computer Science
Dwayne Johnson has got an assignment from his Professor of TOC. He has the alphabet set E = {a, b, (, ), U, *, Ø}. Dwayne Johnson has to make a context-free grammar which generate all string in E* which are regular expressions over the set {a, b}. If Dwayne Johnson can do this he will be promoted to the elite section but if he fails he will be demoted. You have to help Dwayne go to elite section by doing this task for him.
Let G be the following grammar: S → aABbCD A - ASd|ɛ B → SAC |hC |E C→ Sf|Cg D - ED |E The number of productions that will remain in G after elimination of all null productions
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.
(a) Exhibit a derivation of the string aaaa using the following phrase structured grammar: S → YZY Z → BZC| E ВС Сав Ва — ав аС — Са BY → Y ҮС — Y Y → E (b) Find a match for the following instance of the Post Correspondence Problem (PCP): {=} {三目圖} b a bb
Give solution Theory of Automata
Given a regular grammar G and a list of strings, identify the strings that are in L(G).