Recent questions tagged context-free-language - GATE Overflow

First time here? Checkout the FAQ!

x

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

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

0 votes

1 answer

3

Exam - Foundation of Computing - 2018
Find a context-free grammar for the following language: L = { a^m b^m c^k | k <= m } (in order to show that the language is context-free)

asked Apr 11 in Theory of Computation by Melissa (7 points) | 32 views

+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

+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

+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

+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

0 votes

0 answers

8

Peter Linz Exercise 6.1.9
Eliminate all unit-productions from the grammar $S \rightarrow a | aA| B|C,$ $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

+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

+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 context-free? $L1$ only $L3$ Only $L1$ and $L2$ $L2$ ... and then pop two $0's$ for every zero in the stack. So , it is context-free 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

+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

+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

+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

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

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

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

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

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

+12 votes

12 answers

19

GATE2018-35
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 context-free? 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

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

+1 vote

0 answers

21

Regular - Context Free?
Let L be a given context-free 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

+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

+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

+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

+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

+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

+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

+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

+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

+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

Page:

1
2
3
4
5
6
...
10
next »

Follow @csegate

Gatecse

Recent questions tagged context-free-language

34,770 questions

41,730 answers

118,876 comments

41,381 users