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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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.
Recent questions tagged contextfreelanguage
0
votes
1
answer
1
Context Free Languages
Answer with explanation will be acknowledged.
asked
6 days
ago
in
Theory of Computation
by
Subham Nagar
(
405
points)

41
views
contextfreelanguage
theoryofcomputation
contextfreelanguages
0
votes
1
answer
2
Introduction to Computer Theory
Give CFG for the following language L =$ {(a^{m})(b^{m+n})(c^{n})  m,n= 0,1,2,.....}$
asked
Apr 12
in
Theory of Computation
by
The Capricorn
(
133
points)

38
views
theoryofcomputation
contextfreelanguage
0
votes
1
answer
3
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
in
Theory of Computation
by
Melissa
(
7
points)

32
views
contextfreelanguage
contextfreegrammars
+1
vote
0
answers
4
whether the given languages are context free or not
asked
Apr 8
in
Theory of Computation
by
Sambit Kumar
Active
(
2k
points)

76
views
theoryofcomputation
contextfreelanguage
+2
votes
0
answers
5
Theory of computations(CFG)
$L1$ has the following grammar: $S \rightarrow aB/BA$ $A\rightarrow bAA/aS/a$ $B\rightarrow b/bS/aBB$ can someone help me with an easy way to get the general expression for string belonging to this language. Or some hint that how should I proceed to solve this question.
asked
Mar 29
in
Theory of Computation
by
hrcule
(
113
points)

41
views
theoryofcomputation
contextfreelanguage
+4
votes
1
answer
6
Context Free Languages
Which of these languages are deterministic? $L_{1} =$ $\left \{a^{n}b^{n}: n \geq 1 \right \}\cup \left \{ b \right \}$ $L_{2} =$ $\left \{a^{n}b^{n}: n \geq 1 \right \}\cup \left \{ a \right \}$
asked
Mar 28
in
Theory of Computation
by
Mk Utkarsh
Boss
(
11.7k
points)

118
views
contextfreelanguage
theoryofcomputation
+2
votes
0
answers
7
CFG to GNF
Convert the given CFG to GNF. $S \rightarrow MN$ $M\rightarrow aMb\epsilon $ $N\rightarrow aNb\epsilon $
asked
Mar 25
in
Theory of Computation
by
Mk Utkarsh
Boss
(
11.7k
points)

58
views
theoryofcomputation
contextfreelanguage
cnf
gnf
0
votes
0
answers
8
Peter Linz Exercise 6.1.9
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
in
Theory of Computation
by
Mk Utkarsh
Boss
(
11.7k
points)

40
views
theoryofcomputation
peterlinz
contextfreelanguage
+1
vote
2
answers
9
Self_doubt
C1: For DFA (ϕ, Ʃ, δ, qo, F), if F = ϕ, then L = Ʃ* C2: For NFA (ϕ, Ʃ, δ, qo, F), if F = ϕ, then L = Ʃ* Where F = Final states set ϕ = Total states set Choose the correct option ? Both are true Both are False $C1$ is true, $C2$ is false $C1$ is false, $C2$ is true What is the answer and also explain that?
asked
Mar 22
in
Theory of Computation
by
Raj Kumar 7
Junior
(
837
points)

32
views
theoryofcomputation
contextfreelanguage
+3
votes
2
answers
10
Gate 2006
Let $L_1 = \{0^{n+m}1^n0^m \mid n,m \geq 0\},L_2\{0^{n+m}1^{n+m}0^m \mid n,m\geq 0\}$, and $L_3\{0^{n+m}1^{n+m}0^{n+m} \mid n,m\geq 0\}$, which of these languages are NOT contextfree? $L1$ only $L3$ Only $L1$ and $L2$ $L2$ ... and then pop two $0's$ for every zero in the stack. So , it is contextfree language. But Answer is D. How $L3$ is context free language ? Explain how am i wrong.
asked
Mar 22
in
Theory of Computation
by
Raj Kumar 7
Junior
(
837
points)

48
views
gate
gate2006
theoryofcomputation
contextfreelanguage
+1
vote
1
answer
11
Gate 2009
$S > aSa\mid bSb \mid a \mid b$; The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of All palindromes All odd length palindromes. Strings that begin and end with the same symbol All even length palindromes I think answer is B & C both but anwer is only B given not C. Why? plz explain .......
asked
Mar 22
in
Theory of Computation
by
Raj Kumar 7
Junior
(
837
points)

30
views
gate
gate2009
theoryofcomputation
contextfreelanguage
+1
vote
0
answers
12
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
in
Theory of Computation
by
Mk Utkarsh
Boss
(
11.7k
points)

58
views
contextfreelanguage
theoryofcomputation
contextfreegrammars
+1
vote
1
answer
13
Peter Linz Exercise 5.1 Ques.7(c)
Find CFG for the following language L = $\left \{ a^{n}b^{m}: n \neq 2m \right \}$
asked
Mar 20
in
Theory of Computation
by
Mk Utkarsh
Boss
(
11.7k
points)

120
views
theoryofcomputation
peterlinz
contextfreelanguage
0
votes
1
answer
14
Introduction to Computer Theory
Write the CFG (Context Free Grammar) for the given condition: ((a^n).(b^(2n + 1)))
asked
Mar 17
in
Theory of Computation
by
The Capricorn
(
133
points)

17
views
theoryofcomputation
contextfreelanguage
0
votes
1
answer
15
Finding whether given languages are regular or context free
asked
Mar 2
in
Theory of Computation
by
GateAspirant999
Active
(
2.5k
points)

45
views
regularlanguages
contextfreelanguage
0
votes
2
answers
16
Simple Grammar
Consider Grammar G with the following characteristic $A → ax$, where $A ∈ V$, $a ∈ T$, $x ∈ V^*$, and any pair $( A, a )$ occurs at most once in $P$. For example, $S → aA \mid aB...,$ is not a grammar of type $G$ because the pair $(S,a)$ occur in two productions. ... string w belonging to $L(G)$ ? $\mid w \mid^3$ $\mid w \mid$ $2^{\mid w \mid}$ Not a function of $\mid w \mid$ alone.
asked
Feb 24
in
Theory of Computation
by
tarun_svbk
Active
(
1.5k
points)

46
views
theoryofcomputation
contextfreelanguage
peterlinz
grammar
cfg
0
votes
0
answers
17
Sentential forms
Restricting only to the leftmost derivations, how many sentential forms can exhaustive search parsing generate ? $O(P^{\mid w \mid})$ $O(P^{\mid w \mid +1})$ $O(P^{2\mid w \mid})$ $O(P^{2\mid w \mid + 1})$ where, $P$ is the number of productions and w is the word to be generated.
asked
Feb 24
in
Theory of Computation
by
tarun_svbk
Active
(
1.5k
points)

25
views
theoryofcomputation
contextfreelanguage
peterlinz
grammar
0
votes
0
answers
18
IA Languages
Consider the language $L = \{a^nb^nc^m\}U \{a^nb^mc^m\}$ with $n$ and $m$ nonnegative. Which of the following options is correct? There is no context free grammar possible for $L$. There exists a simple grammar for $L$. There exists an unambiguous grammar for $L$. There exists an ambiguous grammar for $L$.
asked
Feb 24
in
Theory of Computation
by
tarun_svbk
Active
(
1.5k
points)

38
views
theoryofcomputation
contextfreelanguage
peterlinz
grammar
+12
votes
12
answers
19
GATE201835
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text ... =p+q, \text{ where } m, n, p, q \geq 0 \}$ Which of the above languages are contextfree? I and IV only I and II only II and III only II and IV only
asked
Feb 14
in
Theory of Computation
by
gatecse
Boss
(
17.7k
points)

2.1k
views
gate2018
theoryofcomputation
identifyclasslanguage
contextfreelanguage
normal
0
votes
1
answer
20
Complement of CFL
How to prove that $\text{"complement of L }= \{WW^R \mid W \in \{a,b\}^*\} \text{ is CFL}" $?
asked
Feb 10
in
Theory of Computation
by
ankitgupta.1729
Active
(
4.2k
points)

92
views
contextfreelanguage
theoryofcomputation
+1
vote
0
answers
21
Regular  Context Free?
Let L be a given contextfree language over the alphabet {a, b}. Construct L1, L2 as follows. Let L1 = L − {xyx  x, y ∈ {a, b}∗}, and L2 = L·L. Then, (A) Both L1 and L2 are regular. B) Both L1 and L2 are context free but not necessarily regular. (C) L1 is regular and L2 is context free. (D) L1 and L2 both may not be context free
asked
Jan 30
in
Theory of Computation
by
Tuhin Dutta
Loyal
(
7.5k
points)

60
views
theoryofcomputation
contextfreelanguage
regularlanguages
+2
votes
1
answer
22
Made easy test
(a^n)^m b^n where n>=0 and m>1 is a) regular b) cfl c) csl d) none
asked
Jan 29
in
Theory of Computation
by
♥_Less
Junior
(
957
points)

68
views
madeeasytestseries
regularexpressions
regularlanguages
contextfreelanguage
contextsensitive
+1
vote
0
answers
23
Compiler: Ambiguous Grammar
Consider the following grammars: Grammar G1: S → 0 T  ε T → 1 S Grammar G2: S → T S S → ε T → X Y X → 0 Y → 1 Which of the following statements is not true? A. Grammar G1 can generate any string that G2 can, and ... . Grammar G1 corresponds to a regular language. D. Grammar G1 corresponds to a language that can be recognized with an LR parser. Is G2 ambiguous grammar?
asked
Jan 20
in
Compiler Design
by
Vijay Thakur
Boss
(
17k
points)

59
views
theoryofcomputation
compilerdesign
ambiguous
contextfreelanguage
+1
vote
0
answers
24
Toc dfa
Is this DCFL or not a^n b^2n c^3n. n>=1 My logic is Push all a's Pop one a with one b After remain b push on stack After pop one b With 3c
asked
Jan 19
in
Theory of Computation
by
Nitesh Choudhary
Active
(
2.5k
points)

35
views
theoryofcomputation
contextfreelanguage
+2
votes
1
answer
25
CFG and CSL
My doubt may be silly but plz help. Given a particular language how to know whether a grammar is CFL or CSL sometimes it really creates me a problem Language like {a^n b^n c^2n n > 0} is a CSL but if suppose it was a new random question than ... its PDA so it should be CFL. SO How to tackle such question in first attempt if before hand we don't know anything about the language
asked
Jan 17
in
Theory of Computation
by
Na462
Active
(
1.6k
points)

36
views
theoryofcomputation
contextfreelanguage
+3
votes
2
answers
26
TOC DFA
I got 3 states... Given is 4
asked
Jan 16
in
Theory of Computation
by
Ashwin Kulkarni
Boss
(
17.5k
points)

73
views
theoryofcomputation
regularlanguages
contextfreelanguage
+2
votes
0
answers
27
cfl or not
the condition is 1) (i<=j) or (j<=i) , j=k 2) (i<=j) or (j<=i) ,j=k how should we interpret the condition given ?
asked
Jan 12
in
Theory of Computation
by
gari
Active
(
3.2k
points)

31
views
theoryofcomputation
contextfreelanguage
+3
votes
0
answers
28
Decidability
a) L is decidable b) L is undecidable c) L is regular d) None of these
asked
Jan 10
in
Theory of Computation
by
Nymeria
(
401
points)

106
views
decidability
contextfreelanguage
turingmachine
reduction
+2
votes
1
answer
29
Context Free Language
Is B context free? Please explain in detail.
asked
Jan 6
in
Theory of Computation
by
Shubham Kumar Gupta
Junior
(
513
points)

158
views
contextfreelanguage
theoryofcomputation
identifyclasslanguage
regularlanguages
grammar
+1
vote
1
answer
30
closure property
CFL over a single alphabet are always> A. dcfl B. regular C. dcfl but not regular d. non regular
asked
Dec 30, 2017
in
Theory of Computation
by
raviyogi
Active
(
2.5k
points)

64
views
theoryofcomputation
contextfreelanguage
closureproperty
regularlanguages
Page:
1
2
3
4
5
6
...
10
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
Placement Statistics for Computer Science
IIT Bombay Admission
ISRO 2018
NTRO Final year Eligibility
Fake Accounts
Follow @csegate
Gatecse
Recent questions tagged contextfreelanguage
Recent Blog Comments
Did you clear the test? Were you selected?
No. There was no penalty. We were allowed to ...
You have to write the entire code. I attempted 5 ...
Let's say c = 5 and p = ...
In this problem we need to choose p integers from ...
34,770
questions
41,730
answers
118,876
comments
41,381
users