Recent questions tagged context-free-grammars - GATE Overflow

0 votes

1 answer

1

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 | 183 views

+1 vote

1 answer

2

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 | 156 views

+2 votes

1 answer

3

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 non-ambiguous and that of NFA is ambiguous

asked Jan 8, 2018 in Compiler Design by Venkat Sai | 145 views

+5 votes

1 answer

4

NIELT 2017 Question
Let G be a grammar in CFG and Let W1 and W2 is element of G such that |w1| = |w2| then which of the following is true? A. Any derivation of W1 has exactly the same number of steps as any derivation of W2 B. Different derivation have different length C.Some derivation of W1 may be shorter that derivation of W2 D. None of the options

asked Dec 18, 2017 in Theory of Computation by Durgesh Singh | 1.2k views

+3 votes

2 answers

5

ISRO-DEC2017-23
Identify the language generated by the following grammar $S\rightarrow AB\\ A\rightarrow aAb\mid \varepsilon\\ B\rightarrow bB\mid b$ $\{a^m b^n\mid n\geq m,m>0\}$ $\{a^m b^n\mid n\geq m,m\geq0\}$ $\{a^m b^n\mid n> m,m>0\}$ $\{a^m b^m\mid n> m,m\geq0\}$

asked Dec 17, 2017 in Theory of Computation by gatecse | 881 views

0 votes

0 answers

6

Context free or not
How to understand such problems?

asked Nov 20, 2017 in Theory of Computation by Parshu gate | 156 views

0 votes

0 answers

7

regular and context free
Let Σ = {a, b}. For a word w ∈ Σ* , let na(x) denote the number of a’s in w and let nb(x) denote the number of b’s in w. Consider the following language: L := {xy | x, y ∈ Σ* , na(x) = nb(y)} What can we say about L? (A) L is regular, but not context-free. (B) L is context-free, but not regular. (C) L is Σ*. (D) None of these.

asked Nov 15, 2017 in Theory of Computation by Parshu gate | 46 views

0 votes

1 answer

8

#TOC Someone please Explain this Gate Question
This is the Gate Question - https://gateoverflow.in/3392/gate2008-it-78?show=155376#c155376 I couln't help but understand the balanced paranthesis thing, I know, () this is balanced, (( )) is balanced, ((( ))) is balanced, ... t have any intention to make a duplicate question/thread, I will close this question whenever I get my doubt solved. Thanks!

asked Sep 26, 2017 in Theory of Computation by iarnav | 117 views

0 votes

1 answer

9

#Parsing
Grammar : E->T+E/T T->id/id*T/(E) Is grammar LL(2)?

asked Sep 26, 2017 in Compiler Design by saxena0612 | 146 views

0 votes

3 answers

10

UGCNET-dec2009-ii-34
Contex-free Grammar (CFG) can be recognized by (A) Finite state automata (B) 2-way linear bounded automata (C) push down automata (D) both (B) and (C)

asked Sep 17, 2017 in Theory of Computation by rishu_darkshadow | 168 views

+1 vote

1 answer

11

context- free grammers
L = {a^nb^m : n >= m+3} below context grammer is correct?? S ==> aA | Aa A ==> aAb | bAa | abA | baA | aa

asked Jul 12, 2017 in Theory of Computation by akhileshreddy | 112 views

0 votes

1 answer

12

dr.O.G. kakde, context free grammar and syntax analysis
obtain regular grammar equivalent to the regular expression given below: 1) a*(a|b)bb 2) (ab)*ba(ab)*

asked Jun 28, 2017 in Compiler Design by RAJKUMAR | 146 views

+1 vote

0 answers

13

UGCNET-AUG2016-III: 57
Let $G = (V, T, S, P)$ be a context-free grammar such that every one of its productions is of the form $A \rightarrow ν$, with $|ν| = k > 1$. The derivation tree for any string $W \in L (G)$ has a height such that $h < \frac{(|W|-1)}{k-1}$ $\log_{k} |W| \leq h$ $\log_{k} |W| < h < \frac{(|W|-1)}{k-1}$ $\log_{k} |W| \leq h \leq \frac{(|W|-1)}{k-1}$

asked Oct 5, 2016 in Theory of Computation by makhdoom ghaya | 246 views

+3 votes

2 answers

14

UGCNET-June2015-III: 61
A context free grammar for $L=\{w \mid n_0 (w) > n_1 (w)\}$ is given by: $S \rightarrow 0 \mid 0S \mid 1 S S$ $S \rightarrow 0 S \mid 1 S \mid 0 S S \mid 1 S S \mid 0 \mid 1$ $S \rightarrow 0 \mid 0 S \mid 1 S S \mid S 1 S \mid S S 1$ $S \rightarrow 0 S \mid 1 S \mid 0 \mid 1$

asked Aug 2, 2016 in Theory of Computation by jothee | 1.1k views

+2 votes

2 answers

15

UGCNET-Dec2013-II: 27
The context free grammar for the language: $L=\{a^n b^m \mid n \leq m + 3, n \geq 0, m \geq 0 \}$ is $S \rightarrow aaa \quad A; A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$ ... $S \rightarrow aaaA \mid aa \quad A \mid aA \mid \lambda, A \rightarrow aAb \mid B, B \rightarrow Bb \mid \lambda$

asked Jul 26, 2016 in Theory of Computation by jothee | 969 views

+1 vote

6 answers

16

UGCNET-Dec2014-II: 35
The following Context-Free Grammar (CFG) : $S \rightarrow aB | bA$ $A \rightarrow a | as | bAA$ $B \rightarrow b | bs | aBB$ will generate Odd numbers of $a's$ and odd numbers of $b's$ Even numbers of $a's$ and even numbers of $b's$ Equal numbers of $a's$ and $b's$ Different numbers of $a's$ and $b's$

asked Jul 23, 2016 in Theory of Computation by makhdoom ghaya | 715 views

+3 votes

1 answer

17

UGCNET-June2013-III: 38
For every context free grammar (G) there exists an algorithm that passes any $w \in L(G)$ in number of steps proportional to $ln\mid w \mid$ $\mid w \mid$ $\mid w \mid^2$ $\mid w \mid^3$

asked Jul 17, 2016 in Theory of Computation by jothee | 813 views

+9 votes

1 answer

18

ISI2013-PCB-CS-4a
Give a context-free grammar $G$ that generates $L = \{0^i1^j0^k \mid i + k = j\}$. Prove that $L = L(G)$.

asked Jun 1, 2016 in Theory of Computation by jothee | 429 views

Page:

« prev
1
2
3
4
5
6
7

Recent questions tagged context-free-grammars

52,345 questions

60,497 answers

201,860 comments

95,316 users