The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged contextfreegrammars
0
votes
0
answers
1
Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 10 (Page No. 233)
Show how, having filled in the table as in Question $4.4.9$, we can in $O(n)$ time recover a parse tree for $a_{1}a_{2}\cdot\cdot\cdot a_{n}$. Hint: modify the table so it records, for each nonterminal $A$ in each table entry $T_{ij}$, some pair of nonterminals in other table entries that justified putting $A$ in $T_{ij}$.
asked
4 days
ago
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

2
views
ullman
compilerdesign
contextfreegrammars
descriptive
0
votes
0
answers
2
Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 9 (Page No. 232)
Every language that has a contextfree grammar can be recognized in at most $O(n^{3})$ time for strings of length $n$. A simple way to do so,called the Cocke YoungerKasami (or CYK) algorithm is based on dynamic programming. ... a_{l}a_{2}\cdot\cdot\cdot a_{n} is in the language?
asked
4 days
ago
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

2
views
ullman
compilerdesign
contextfreegrammars
cyk
descriptive
0
votes
0
answers
3
Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 3 (Page No. 207)
Design grammars for the following languages: The set of all strings of $0's$ and $1's$ such that every $0$ is immediately followed by at least one $1$. The set of all strings of $0's$ and $1's$ that are palindromes; that is, the string ... $1's$ of the form $xy$, where $x\neq y$ and $x$ and $y$ are of the same length.
asked
Aug 17
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

1
view
ullman
compilerdesign
contextfreegrammars
descriptive
0
votes
0
answers
4
Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 2 (Page No. 206  207)
Repeat Question $4.2.1$ for each of the following grammars and strings: $S\rightarrow 0S1\mid 01$ with string $000111$. $S\rightarrow +SS\mid \ast SS\mid a$ with string $+\ast aaa$ ... $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$
asked
Aug 17
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

5
views
ullman
compilerdesign
contextfreegrammars
parsetree
ambiguous
descriptive
0
votes
1
answer
5
Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 1 (Page No. 206)
Consider the contextfree grammar:$S\rightarrow SS + \mid SS {\ast} \mid a$and the string $aa + a{\ast}$. Give a leftmost derivation for the string. Give a rightmost derivation for the string. ... for the string. Is the grammar ambiguous or unambiguous? Justify your answer. Describe the language generated by this grammar.
asked
Aug 7
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

28
views
ullman
compilerdesign
contextfreegrammars
parsetree
ambiguous
descriptive
0
votes
0
answers
6
Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 6 (Page No. 52)
Construct a contextfree grammar for roman numerals.
asked
Jul 26
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

2
views
ullman
compilerdesign
contextfreegrammars
0
votes
0
answers
7
Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 4 (Page No. 51  52)
Construct unambiguous contextfree grammars for each of the following languages. In each case show that your grammar is correct. Arithmetic expressions in postfix notation. Leftassociative lists of identifiers separated by commas. Right ... $(d)$.
asked
Jul 26
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

5
views
ullman
compilerdesign
contextfreegrammars
+1
vote
2
answers
8
Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 3 (Page No. 51)
Which of the grammars are ambiguous? $S\rightarrow 0S1 \mid 01$ $S\rightarrow +SS \mid SS \mid a$ $S\rightarrow S(S)S \mid \epsilon$ $S\rightarrow aSbS \mid bSaS \mid \epsilon$ $S\rightarrow a \mid S+S \mid SS \mid S^{\ast} \mid (S)$
asked
Jul 26
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

17
views
ullman
compilerdesign
contextfreegrammars
ambiguous
0
votes
0
answers
9
Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 2 (Page No. 51)
What language is generated by the following grammars? In each case justify your answer. $S\rightarrow 0S1 \mid 01$ $S\rightarrow +SS \mid SS \mid a$ $S\rightarrow S(S)S \mid \epsilon$ $S\rightarrow aSbS \mid bSaS \mid \epsilon$ $S\rightarrow a \mid S+S \mid SS \mid S^{\ast} \mid (S)$
asked
Jul 26
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

3
views
ullman
compilerdesign
contextfreegrammars
0
votes
0
answers
10
Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 1 (Page No. 51)
Consider the contextfree grammar $S\rightarrow SS+\mid SS^{\ast}\mid a$ Show how the string $aa+a^{\ast}$ can be generated by this grammar. Construct a parse tree for this string. What language does this grammar generate? Justify your answer.
asked
Jul 26
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

1
view
ullman
compilerdesign
contextfreegrammars
0
votes
0
answers
11
Ullman (TOC) Edition 3 Exercise 9.5 Question 1 (Page No. 418)
Let $L$ be the set of (codes for) contextfree grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.
asked
Jul 26
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

4
views
ullman
theoryofcomputation
contextfreegrammars
pcp
descriptive
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 7.4 Question 9 (Page No. 204)
Give LL grammars for the following languages, assuming $Σ =$ {$a,b, c$}. (i) $L=$ {$a^nb^mc^{n+m}:n\geq0,m\geq0$} . (ii) $L=$ {$a^{n+2}b^mc^{n+m}:n\geq0,m\geq0$} . (iii) $L=$ {$a^nb^{n+2}c^{m}:n\geq0,m\gt1$} . (iv) $L=$ {$w:n_a(w)\lt n_b(w)$} . (v) $L=$ {$w:n_a(w)+n_b(w)\neq n_c(w)$} .
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

16
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 7.4 Question 8 (Page No. 204)
Let G be a contextfree grammar in Greibach normal form. Describe an algorithm which, for any given k, determines whether or not G is an LL (k) grammar.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

11
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 7.4 Question 6 (Page No. 204)
Show that if G is an LL (k) grammar, then L (G) is a deterministic contextfree language.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 7.4 Question 5 (Page No. 204)
Show that any LL grammar is unambiguous.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
16
Peter Linz Edition 4 Exercise 7.4 Question 4 (Page No. 204)
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 7.4 Question 3 (Page No. 204)
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 7.4 Question 2 (Page No. 204)
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

7
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 7.4 Question 1 (Page No. 204)
Show that the grammar $S_0\rightarrow aSbS,S\rightarrow aSbS\lambda$ is an LL grammar and that it is equivalent to the grammar $S\rightarrow SSaSbab$.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

8
views
peterlinz
theoryofcomputation
contextfreegrammars
+1
vote
1
answer
20
ISI2018PCBB4
Let the valid moves along a staircase be $U$ (one step up) and $D$ (one step down). For example, the string $s = UUDU$ represents the sequence of moves as two steps up, then one step down, and then again one step up. Suppose a person is initially ... returns to the base of the staircase after the final step. Show that $L$ is not regular Write a context free grammar for accepting $L$
asked
May 12
in
Theory of Computation
by
akash.dinkar12
Boss
(
41.3k
points)

28
views
isi2018pcbb
theoryofcomputation
contextfreegrammars
descriptive
0
votes
1
answer
21
Michael Sipser Edition 3 Exercise 2 Question 28 (Page No. 157)
Give unambiguous $CFG's$ for the following languages$.$ $\text{{$w\mid$ in every prefix of $w$ the number of $a’s$ is at least the number of $b’s$}}$ $\text{{$w\mid$ the number of $a’s$ and the number of $b’s$ in $w$ are equal}}$ $\text{{$w\mid$ the number of $a’s$ is at least the number of $b’s$ in $w$}}$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

22
views
michaelsipser
theoryofcomputation
contextfreegrammars
0
votes
1
answer
22
Michael Sipser Edition 3 Exercise 2 Question 27 (Page No. 157)
$G$ is a naturallooking grammar for a fragment of a programming language, but $G$ is ambiguous$.$ Show that $G$ is ambiguous$.$ Give a new unambiguous grammar for the same language$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

20
views
michaelsipser
theoryofcomputation
contextfreegrammars
ambiguousgrammar
+1
vote
1
answer
23
Michael Sipser Edition 3 Exercise 2 Question 26 (Page No. 157)
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

23
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
proof
0
votes
1
answer
24
Michael Sipser Edition 3 Exercise 2 Question 22 (Page No. 156)
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a contextfree language$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

22
views
michaelsipser
theoryofcomputation
contextfreegrammars
0
votes
1
answer
25
Michael Sipser Edition 3 Exercise 2 Question 21 (Page No. 156)
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

9
views
michaelsipser
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 2 Question 19 (Page No. 156)
Let $CFG$ $G$ be the following grammar$.$ $S\rightarrow aSb \mid bY \mid Y a$ $Y\rightarrow bY \mid aY \mid \epsilon$ Give a simple description of $L(G)$ in English$.$ Use that description to give a $CFG$ for $\overline{L(G)},$ the complement of $L(G).$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

10
views
michaelsipser
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 2 Question 15 (Page No. 156)
Give a counterexample to show that the following construction fails to prove that the class of contextfree languages is closed under star. Let $A$ be a $\text{CFL}$ that is generated by the $\text{CFG}$ ... new rule $S\rightarrow SS$ and call the resulting grammar $G'.$This grammar is supposed to generate $A^{*}.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

12
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
1
answer
28
Michael Sipser Edition 3 Exercise 2 Question 14 (Page No. 156)
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$ $A\rightarrow BAB \mid B \mid \epsilon$ $B\rightarrow 00 \mid \epsilon$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

20
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
0
votes
1
answer
29
Michael Sipser Edition 3 Exercise 2 Question 13 (Page No. 156)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T0\mid \#$ $U\rightarrow 0U00\mid\#$ Describe $L(G)$ in English. Prove that $L(G)$ is not regular$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

22
views
michaelsipser
theoryofcomputation
contextfreegrammars
regularlanguages
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 2 Question 12 (Page No. 156)
Convert the $CFG$ $G$ $R\rightarrow XRX \mid S$ $S\rightarrow aT b \mid bT a$ $T\rightarrow XT X \mid X \mid\epsilon$ $X\rightarrow a \mid b$ to an equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$
asked
May 2
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

19
views
michaelsipser
theoryofcomputation
contextfreegrammars
pushdownautomata
Page:
1
2
3
4
5
6
next »
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged contextfreegrammars
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,809
answers
189,534
comments
80,845
users