Consider the following CFG with alphabet {a, b} and start variable S: S- AB A - aAa B- ÞBb What is the shortest string in the language of the grammar excluding the empty string? b. Draw the derivation tree for the string in (a). c. Explain whether this grammar is ambiguous or not? d. Describe in English the language generated by the grammar. e. Explain why this CFG can or cannot generate a regular language. a.

Consider the following CFG with alphabet {a, b} and start variable S: S- AB A - aAa B- ÞBb What is the shortest string in the language of the grammar excluding the empty string? b. Draw the derivation tree for the string in (a). c. Explain whether this grammar is ambiguous or not? d. Describe in English the language generated by the grammar. e. Explain why this CFG can or cannot generate a regular language. a.

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

Create a parse tree of the string accepted by the grammar. Given the grammar S→ aS|aSbS|ε a. aaaaaaaaaa b. abababababab c. aabbaabbaa d. aaaaabaaaaa e. bbbaaaaaaaaa
grammar is ambigous or not?
2. Given the grammar below, without any modifications, is it LL(1) in its current form and why yes or no? (Need to compute First() sets and check intersections, separately for each nonterminal). If not LL(1), rewrite as LL(1) and verify it is (do the same all over). S -> abCS | abC | AC A -> bA|bb C -> cC | D D -> dd
A lexical analyzer cannot be created for a language whose grammar: a. lacks pairwise disjointnessb. has left-recursionc. is ambiguousd. a and b onlye. b and c onlyf. and c onlyg. a, b, and ch. none of the above
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.
Correct and detailed answer will be Upvoted Construct a context free grammar for all binary strings having even number of 0s. Show step-by-step solution.
Computer Science Consider the following two grammars with alphabet a and b i. (b*ab*a)*b* ii. (b*ab*a)*b*(b*ab*a)*b* Are there any strings are generated by one of the grammars and cannot be generated by the other? If there are more than one such string, how do you describe them.
Is the grammar LL(1)? Why or why not? If grammar is LL(1), use your parsing table to derive the string: modifier noun verb modifier
The set of all syntactically valid strings representing regular expressions is A. a regular language, because a regular expression can describe this language B. a context-free language and it can be generated by a context-free grammar but not by any regular grammar O C. a context-sensitive language but not by any context-free grammar
The set of strings with an equal number of a's, b's, c's and d's, in any random order, can be described by which kind of grammar? OA. A regular grammar B. A context-free grammar but not by any regular grammar C. A context-sensitive grammar but not by any context-free grammar OD. None of the above, since no grammar can generate this language
5. How to convert a Regular Expression to left-linear grammar (0+1)*00(0+1)* 6. Define regular expression and regular set. Find an equivalent regular expression to the following DFA- qo