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
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.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 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

38
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
2
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 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

16
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
3
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 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

9
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
4
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 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

6
views
ullman
theoryofcomputation
contextfreegrammars
0
votes
1
answer
5
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 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

17
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
6
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 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

34
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
7
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 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

15
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
8
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

21
views
ullman
theoryofcomputation
regularexpressions
contextfreegrammars
0
votes
0
answers
9
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

15
views
ullman
theoryofcomputation
contextfreegrammars
regularlanguages
0
votes
0
answers
10
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

18
views
ullman
theoryofcomputation
contextfreegrammars
regularexpressions
0
votes
0
answers
11
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

10
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
12
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
in
Compiler Design
by
aditi19
Active
(
5.1k
points)

43
views
theoryofcomputation
compilerdesign
contextfreegrammars
+1
vote
1
answer
13
Ullman Exercise
What language is generated by the following grammer? S→ a  S+S  SS  S*  (S)
asked
Mar 19
in
Compiler Design
by
aditi19
Active
(
5.1k
points)

38
views
compilerdesign
contextfreegrammars
0
votes
1
answer
14
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 10
in
Theory of Computation
by
s_dr_13
(
179
points)

35
views
theoryofcomputation
contextfreegrammars
0
votes
1
answer
15
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
in
Theory of Computation
by
aditi19
Active
(
5.1k
points)

124
views
contextfreelanguage
theoryofcomputation
contextfreegrammars
0
votes
1
answer
16
CFG Doubt
S>A  B A→ ε B>aBb B>b what is the complement of the language of this grammar?
asked
Mar 2
in
Theory of Computation
by
aditi19
Active
(
5.1k
points)

122
views
contextfreelanguage
theoryofcomputation
contextfreegrammars
0
votes
1
answer
17
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
in
Theory of Computation
by
aditi19
Active
(
5.1k
points)

127
views
theoryofcomputation
peterlinz
contextfreelanguage
contextfreegrammars
0
votes
1
answer
18
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
Active
(
5.2k
points)

99
views
theoryofcomputation
pushdownautomata
dpda
contextfreegrammars
0
votes
0
answers
19
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 18, 2018
in
Theory of Computation
by
Sambhrant Maurya
Active
(
3.5k
points)

66
views
theoryofcomputation
contextfreegrammars
contextfreelanguage
cfg
pushdownautomata
0
votes
0
answers
20
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
Loyal
(
7.3k
points)

42
views
theoryofcomputation
contextfreegrammars
0
votes
0
answers
21
Context Free Grammar
What is the difference between "arbitrary CFG" and "CFG"?
asked
Aug 25, 2018
in
Compiler Design
by
rhcemak
(
127
points)

140
views
theoryofcomputation
contextfreegrammars
0
votes
1
answer
22
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
Active
(
5.1k
points)

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

183
views
contextfreegrammars
chomskynormalform
0
votes
0
answers
24
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 14, 2018
in
Theory of Computation
by
hrcule
(
209
points)

75
views
theoryofcomputation
contextfreegrammars
0
votes
1
answer
25
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
(
5
points)

54
views
contextfreelanguage
contextfreegrammars
0
votes
0
answers
26
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
Boss
(
35.7k
points)

106
views
theoryofcomputation
peterlinz
contextfreegrammars
+1
vote
0
answers
27
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
Boss
(
35.7k
points)

156
views
contextfreelanguage
theoryofcomputation
contextfreegrammars
0
votes
1
answer
28
Context free grammar and push down automata.
Is true..? In an unambiguous grammar every string has exactly one derivation.
asked
Mar 21, 2018
in
Theory of Computation
by
hrcule
(
209
points)

146
views
theoryofcomputation
contextfreegrammars
pushdownautomata
+1
vote
1
answer
29
Peter Linz Edition 4 Derivation Trees Definition 5.3 (Page No. 130)
Which of the following is false for derivation tree of CFG $G (V, T, P, S)$ ? The root is labeled $S$. Every leaf has a label from $V ⋃ T ⋃ \{ λ \}$. A vertex with a child labeled $λ$ can only have it as the rightmost child. $\text{1 & 3}$ $\text{1 & 2}$ $\text{2 & 3}$ $\text{Only 2}$
asked
Feb 24, 2018
in
Theory of Computation
by
tarun_svbk
Active
(
1.7k
points)

93
views
theoryofcomputation
peterlinz
contextfreegrammars
derivationtree
+2
votes
1
answer
30
regular grammers ambiguity
are grammars corresponding to DFA's unambiguous and those to NFA's are ambiguous? according to what I studied every DCFL is guaranteed has an unambiguous grammar though there are multiple grammars generating them every regular language is also DCFL hence ... follow the same but I doubt if every grammar corresponding to DFA is nonambiguous and that of NFA is ambiguous
asked
Jan 7, 2018
in
Compiler Design
by
Venkat Sai
Active
(
3.7k
points)

104
views
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged contextfreegrammars
Recent Blog Comments
Great work sir
Yes Sir, It will be very helpful if we get...
@arjun sir is there a pdf...
Really helpful sir Thanks a ton👍👍
Amazing work Sir
50,644
questions
56,536
answers
195,650
comments
101,428
users