Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged context-free-grammar
4
votes
0
answers
211
Ullman (TOC) Edition 3 Exercise 5.4 Question 7 (Page No. 216)
The following grammar generates prefix expressions with operands $x$ and $y$ and binary operators $+,-$ and $*$ $:$ $E\rightarrow +EE|*EE|-EE|x|y$ Find leftmost and rightmost derivations and a derivation tree for the string $+*-xyxy.$ Prove that this grammar is unambiguous.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
749
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
212
Ullman (TOC) Edition 3 Exercise 5.4 Question 6 (Page No. 216)
This question concerns the grammar $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow 0B|1B\in$ Is your grammar is unambiguous$?$ If not,redesign it to be unambiguous.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
282
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
213
Ullman (TOC) Edition 3 Exercise 5.4 Question 5 (Page No. 216)
This question concerns the grammar $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow 0B|1B\in$ Show that this grammar is unambiguous. Find a grammar for the same language that is ambiguous and demonstrate its ambiguity.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
199
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
214
Ullman (TOC) Edition 3 Exercise 5.4 Question 4 (Page No. 216)
Some strings of $a's$ and $b's$ have a unique parse tree in the grammar of $S\rightarrow aS|aSbS|\in.$ Give an efficient test to tell whether a given string is one of these. The test $"$try all parse trees to see how many yield the given string$"$ is not adequately efficient$.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
220
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
215
Ullman (TOC) Edition 3 Exercise 5.4 Question 3 (Page No. 216)
Find an unambiguous grammar for the language of $S\rightarrow aS|aSbS|\in$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
205
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
216
Ullman (TOC) Edition 3 Exercise 5.4 Question 2 (Page No. 216)
Prove that the grammar generates all only the strings of $a's$ and $b's$ such that every prefix has at least as many $a's$ as $b's.$ $S\rightarrow aS|aSbS|\in$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
183
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
217
Ullman (TOC) Edition 3 Exercise 5.4 Question 1 (Page No. 215)
Consider the grammar $S\rightarrow aS|aSbS|\in$ This grammar is ambiguous. Show in particular that the string $aab$ has two$:$ Parse trees Leftmost derivations Rightmost derivations
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
144
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
218
Ullman (TOC) Edition 3 Exercise 5.2 Question 4 (Page No. 193)
If $X_{1}X_{2}.....X_{k}\overset{*}\Rightarrow \alpha,$ then all the positions of $\alpha$ that come from expansion of $X_{i}$ are to the left of all the positions that come from expansion of $X_{j},$ if $i<j.$ Prove this fact$.$ Hint$:$ Perform an induction on the number of steps in the derivation$.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
151
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
219
Ullman (TOC) Edition 3 Exercise 5.2 Question 3 (Page No. 193)
Suppose all is as in question $2,$ but $G$ may have some productions with $\in$ as the right side. Show that a parse tree for a string $w$ other than $\in$ may have as many as $n+2m-1$ nodes,but no more.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
340
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
220
Ullman (TOC) Edition 3 Exercise 5.2 Question 2 (Page No. 193)
Suppose that $G$ is a $CFG$ without any productions that have $\in$ as the right side. If $w$ is in $L(G),$ the length of $w$ is $n$ and $w$ has a derivation of $m$ steps, show that $w$ has a parse tree with $n+m$ nodes.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
181
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
221
Ullman (TOC) Edition 3 Exercise 5.2 Question 1 (Page No. 193)
For the following grammar and each of the strings gives pase trees. $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow B|1B|\in$ $00101$ $1001$ $00011$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
110
views
ullman
theory-of-computation
context-free-grammar
0
votes
1
answer
222
Ullman (TOC) Edition 3 Exercise 5.1 Question 8 (Page No. 183)
Consider the CFG $G$ defi ned by productions$:$ $S\rightarrow aSbS|bSaS|\in$ Prove that $L(G)$ is the set of all strings with an equal number of $a's$ and $b's.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
1.3k
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
1
answer
223
Ullman (TOC) Edition 3 Exercise 5.1 Question 7 (Page No. 183)
Consider the CFG $G$ defi ned by productions$:$ $S\rightarrow aS|Sb|a|b$ Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring. Describe $L(G)$ informally. Justify your answer using part $(a).$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
1.8k
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
224
Ullman (TOC) Edition 3 Exercise 5.1 Question 6 (Page No. 182 - 183)
We defined the relation $\overset{*}\Rightarrow$ with a basis $"\alpha\Rightarrow \alpha $ and an induction that says $\alpha\overset{*}\Rightarrow\beta$ and $\beta\Rightarrow\gamma$ ... $:$ Use induction on the number of steps in the derivation $\beta\overset{*}\Rightarrow\gamma.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
213
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
225
Ullman (TOC) Edition 3 Exercise 5.1 Question 5 (Page No. 182)
Let $T=\{0,1(,),+,*,\phi,e\}.$ We may think of $T$ as the set of symbols used by regular expressions over alphabet $\{0,1\};$ the only difference is that we use $e$ for symbol $\in,$ to avoid potential ... Your task is to design a CFG with set of terminals $T$ that generates exactly the regular expressions with alphabet $\{0,1\}.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
259
views
ullman
theory-of-computation
regular-expression
context-free-grammar
0
votes
0
answers
226
Ullman (TOC) Edition 3 Exercise 5.1 Question 4 (Page No. 182)
A CFG is said to be right-linear if each production body has at most one variable and that variable is at the right end. That is all productions of a right-linear grammar are of the form $A\rightarrow wB$ ... regular language has a right-linear grammar. Hint$:$Start with a DFA and let the variables of the grammar represent states.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
330
views
ullman
theory-of-computation
context-free-grammar
regular-language
0
votes
0
answers
227
Ullman (TOC) Edition 3 Exercise 5.1 Question 2 (Page No. 182)
The following grammar generates the language of regular expression $0^{*}1(0+1)^{*}:$ $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow B|1B|\in$ Give leftmost and rightmost derivations of the following strings$:$ $00101$ $1001$ $00011$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
224
views
ullman
theory-of-computation
context-free-grammar
regular-expression
0
votes
0
answers
228
Ullman (TOC) Edition 3 Exercise 5.1 Question 1 (Page No. 181 - 182)
Design context-free grammars for the following languages$:$ The set $\{0^{n}1^{n}|n\geq 1,\}$that is the set of all strings of one or more $0's$ followed by an equal number of $1's.$ ... $0's$ as $1's.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
302
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
229
Ullman(Second Edition) Exercise 4.2.3. Question (a) (page no-207)
Design grammar for the language- set of all strings of 0s and 1s such that every 0 is immediately followed by at least one 1 is this correct? S->A | 01S A->1AS | ε
aditi19
asked
in
Compiler Design
Mar 22, 2019
by
aditi19
580
views
theory-of-computation
compiler-design
context-free-grammar
1
vote
1
answer
230
Ullman Exercise
What language is generated by the following grammer? S→ a | S+S | SS | S* | (S)
aditi19
asked
in
Compiler Design
Mar 19, 2019
by
aditi19
458
views
compiler-design
context-free-grammar
0
votes
1
answer
231
No of strings of fixed length possible with a given grammar
What is the number of terminal string of length <= 6 generated by the CFG shown below? S -> 0A1 A -> BB1/B B ->A/0/1 Do you have any semantic method to solve such questions based on some pattern that can ... question it is 6,quite simple to derive but I am wondering what if it had been asked no of strings of length n Thanks
s_dr_13
asked
in
Theory of Computation
Mar 10, 2019
by
s_dr_13
374
views
theory-of-computation
context-free-grammar
1
vote
1
answer
232
CFG Doubt
what is the CFG for the language L=w where number of a’s in w+number of b’s in w=number of c’s in w how to approach this?
aditi19
asked
in
Theory of Computation
Mar 7, 2019
by
aditi19
885
views
context-free-language
theory-of-computation
context-free-grammar
0
votes
1
answer
233
CFG Doubt
S->A | B A→ ε B->aBb B->b what is the complement of the language of this grammar?
aditi19
asked
in
Theory of Computation
Mar 2, 2019
by
aditi19
834
views
context-free-language
theory-of-computation
context-free-grammar
0
votes
1
answer
234
Peter Linz Edition 4 Exercise 5.1 Question 13.a (Page No. 134)
L={$a^nb^n | n\geq 0$} please show how $L^2$ is CFL
aditi19
asked
in
Theory of Computation
Mar 1, 2019
by
aditi19
414
views
theory-of-computation
peter-linz
peter-linz-edition4
context-free-language
context-free-grammar
0
votes
1
answer
235
#ComplierDesign #DragonsBook
For any context-free grammar there is a parser that takes at most O (n$^3$ ) time to parse a string of n terminals. True or False?
Reshu $ingh
asked
in
Compiler Design
Feb 9, 2019
by
Reshu $ingh
901
views
compiler-design
context-free-grammar
parsing
true-false
0
votes
1
answer
236
ACE Test series Question on CFG
Shankar Kakde
asked
in
Compiler Design
Jan 24, 2019
by
Shankar Kakde
642
views
compiler-design
grammar
context-free-grammar
ace-test-series
0
votes
1
answer
237
Ace Test Series: Compiler Design - Left Recursion Elimination
Shankar Kakde
asked
in
Compiler Design
Jan 23, 2019
by
Shankar Kakde
1.6k
views
ace-test-series
compiler-design
context-free-grammar
parsing
left-recursion
1
vote
1
answer
238
ME TEST Series question ON CFG
Shankar Kakde
asked
in
Compiler Design
Jan 19, 2019
by
Shankar Kakde
282
views
compiler-design
context-free-grammar
parsing
made-easy-test-series
1
vote
1
answer
239
Applied Course | Mock GATE | Test 1 | Question: 13
Which of the following statement is not correct? $a^nb^nc^m$ is not CFG $a^mb^nc^n$ is deterministic CFG $a^nb^n$ is CFG $a^{800}b^{800}c^{800}$ is CFG
Applied Course
asked
in
Theory of Computation
Jan 16, 2019
by
Applied Course
992
views
applied-course-2019-mock1
theory-of-computation
context-free-grammar
1
vote
1
answer
240
Applied Course | Mock GATE | Test 1 | Question: 60
The left-factoring of the given CFG is $S \rightarrow aBcD \mid aBD \mid daB \mid d$ $B \rightarrow b$ $D \rightarrow d$ $S \rightarrow aBB' \mid d$ $B' \rightarrow cD \mid D$ $B \rightarrow b$ $D \rightarrow d$ ... $B' \rightarrow aB$ $B \rightarrow b$ $D \rightarrow d$ None of them
Applied Course
asked
in
Compiler Design
Jan 16, 2019
by
Applied Course
625
views
applied-course-2019-mock1
compiler-design
context-free-grammar
left-recursion
Page:
« prev
1
...
3
4
5
6
7
8
9
10
11
12
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged context-free-grammar
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...