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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged contextfreegrammars
0
votes
0
answers
1
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 aSaSbS\in$
asked
Apr 7, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

8
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
2
Ullman (TOC) Edition 3 Exercise 5.4 Question 1 (Page No. 215)
Consider the grammar $S\rightarrow aSaSbS\in$ This grammar is ambiguous. Show in particular that the string $aab$ has two$:$ Parse trees Leftmost derivations Rightmost derivations
asked
Apr 7, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

10
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
3
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$.$
asked
Apr 7, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

46
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
4
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+2m1$ nodes,but no more.
asked
Apr 7, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

42
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
5
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.
asked
Apr 7, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

19
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
6
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 B1B\in$ $00101$ $1001$ $00011$
asked
Apr 7, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

11
views
ullman
theoryofcomputation
contextfreegrammars
0
votes
1
answer
7
Ullman (TOC) Edition 3 Exercise 5.1 Question 8 (Page No. 183)
Consider the CFG $G$ defi ned by productions$:$ $S\rightarrow aSbSbSaS\in$ Prove that $L(G)$ is the set of all strings with an equal number of $a's$ and $b's.$
asked
Apr 7, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

41
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
8
Ullman (TOC) Edition 3 Exercise 5.1 Question 7 (Page No. 183)
Consider the CFG $G$ defi ned by productions$:$ $S\rightarrow aSSbab$ 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).$
asked
Apr 7, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

77
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
9
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.$
asked
Apr 7, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

23
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
10
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\}.$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

54
views
ullman
theoryofcomputation
regularexpressions
contextfreegrammars
0
votes
0
answers
11
Ullman (TOC) Edition 3 Exercise 5.1 Question 4 (Page No. 182)
A CFG is said to be rightlinear if each production body has at most one variable and that variable is at the right end. That is all productions of a rightlinear grammar are of the form $A\rightarrow wB$ ... regular language has a rightlinear grammar. Hint$:$Start with a DFA and let the variables of the grammar represent states.
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

47
views
ullman
theoryofcomputation
contextfreegrammars
regularlanguages
0
votes
0
answers
12
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 B1B\in$ Give leftmost and rightmost derivations of the following strings$:$ $00101$ $1001$ $00011$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

36
views
ullman
theoryofcomputation
contextfreegrammars
regularexpressions
0
votes
0
answers
13
Ullman (TOC) Edition 3 Exercise 5.1 Question 1 (Page No. 181  182)
Design contextfree 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.$ ... the form $ww,$ that is, not equal to any string repeated. The set of all strings with twice as many $0's$ as $1's.$
asked
Apr 6, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

16
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
14
Ullman(Second Edition) Exercise 4.2.3. Question (a) (page no207)
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  ε
asked
Mar 22, 2019
in
Compiler Design
by
aditi19

85
views
theoryofcomputation
compilerdesign
contextfreegrammars
+1
vote
1
answer
15
Ullman Exercise
What language is generated by the following grammer? S→ a  S+S  SS  S*  (S)
asked
Mar 19, 2019
in
Compiler Design
by
aditi19

60
views
compilerdesign
contextfreegrammars
0
votes
1
answer
16
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
asked
Mar 11, 2019
in
Theory of Computation
by
s_dr_13

54
views
theoryofcomputation
contextfreegrammars
0
votes
1
answer
17
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?
asked
Mar 7, 2019
in
Theory of Computation
by
aditi19

169
views
contextfreelanguages
theoryofcomputation
contextfreegrammars
0
votes
1
answer
18
CFG Doubt
S>A  B A→ ε B>aBb B>b what is the complement of the language of this grammar?
asked
Mar 2, 2019
in
Theory of Computation
by
aditi19

155
views
contextfreelanguages
theoryofcomputation
contextfreegrammars
0
votes
1
answer
19
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
asked
Mar 1, 2019
in
Theory of Computation
by
aditi19

153
views
theoryofcomputation
peterlinz
peterlinzedition4
contextfreelanguages
contextfreegrammars
0
votes
1
answer
20
Push Down Automata
Consider Ldf set all languages accepted by DPDA by final state,Lef set of all languages accepted by DPDA by Empty stack Then A)Ldf proper subset of Lef. B)Ldf = Lef. C)Lef proper subset of Ldf. D)None .
asked
Nov 6, 2018
in
Theory of Computation
by
Abhisek Tiwari 4

148
views
theoryofcomputation
pushdownautomata
dpda
contextfreegrammars
0
votes
0
answers
21
Context Free Grammar
Consider the following CFG 'G' S> aA/bSS/SS A> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these
asked
Oct 19, 2018
in
Theory of Computation
by
Sambhrant Maurya

100
views
theoryofcomputation
contextfreegrammars
contextfreelanguages
cfg
pushdownautomata
0
votes
0
answers
22
TOC SELF DOUBT
L = { w ∈ {a,b}* : a(w) = b(w) } We're using the notation: a(w) = number of a's in a string w b(w) = number of b's in a string w S⇾ aSbS  bSaS  ε Doubt: Is the same language generated by below grammar also: S⇾ SS  aSb  bSa  ε
asked
Oct 14, 2018
in
Theory of Computation
by
jatin khachane 1

55
views
theoryofcomputation
contextfreegrammars
0
votes
0
answers
23
Context Free Grammar
What is the difference between "arbitrary CFG" and "CFG"?
asked
Aug 25, 2018
in
Compiler Design
by
rhcemak

231
views
theoryofcomputation
contextfreegrammars
0
votes
1
answer
24
Doubt
L(G)={$a^nb^nc^n$  n>=1} S>aAc A>bA  b can someone tell me what is wrong with this approach?
asked
Aug 24, 2018
in
Theory of Computation
by
aditi19

93
views
theoryofcomputation
contextfreegrammars
0
votes
0
answers
25
https://www.geeksforgeeks.org
asked
Jul 25, 2018
in
Theory of Computation
by
Sachin1696

307
views
contextfreegrammars
chomskynormalform
+2
votes
3
answers
26
ISRO201827
A $CFG$ (Context Free Grammar) is said to be in Chomsky Normal Form $(CNF)$, if all the productions are of the form A$\to$ BC or A$\to$ a. Let $G$ be a $CFG$ in $CNF$. To derive a string of terminals of length x, the number of products to be used is: $2x1$ $2x$ $2x+1$ $2^{x}$
asked
Apr 23, 2018
in
Theory of Computation
by
Arjun

1.3k
views
isro2018
contextfreegrammars
theoryofcomputation
0
votes
0
answers
27
Context Free Grammar
Find the rank of A in the given context free grammar A>BC B>a C>b I think the rank of A in this grammar will be 2. Let me know if I am right and if not then please help with the right answer.
asked
Apr 15, 2018
in
Theory of Computation
by
hrcule

111
views
theoryofcomputation
contextfreegrammars
0
votes
1
answer
28
Exam  Foundation of Computing  2018
Find a contextfree grammar for the following language: L = { a^m b^m c^k  k <= m } (in order to show that the language is contextfree)
asked
Apr 11, 2018
in
Theory of Computation
by
Melissa

70
views
contextfreelanguages
contextfreegrammars
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 6.1 Question 9 (Page No. 162)
Eliminate all unitproductions from the grammar $S \rightarrow a  aA BC,$ $A \rightarrow aB  λ,$ $B \rightarrow aA,$ $C \rightarrow aCD,$ $D \rightarrow ddd $
asked
Mar 23, 2018
in
Theory of Computation
by
Mk Utkarsh

122
views
theoryofcomputation
peterlinz
peterlinzedition4
contextfreegrammars
+1
vote
1
answer
30
Linear Ambiguous Context Free Grammar
Please post few examples of Linear Ambiguous Context Free Grammar. It would be helpful if you post grammars for famous languages.
asked
Mar 22, 2018
in
Theory of Computation
by
Mk Utkarsh

267
views
contextfreelanguages
theoryofcomputation
contextfreegrammars
Page:
« prev
1
2
3
4
5
6
7
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
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.2k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged contextfreegrammars
Recent Blog Comments
Very helpful. can't thank you enough! :) :)
@toxicdesire I don't remember the exact...
Will you please tell what they answered to your...
@commenter max marks for part A was 75. They did...
Hope you get selected bhaiya
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,506
answers
201,910
comments
95,341
users