Recent questions tagged context-free-grammars

+5 votes

1 answer

1

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 Junior (755 points) | 743 views

+2 votes

2 answers

2

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 Boss (16.8k points) | 706 views

0 votes

0 answers

3

Context free or not
How to understand such problems?

asked Nov 20, 2017 in Theory of Computation by Parshu gate Active (3.1k points) | 124 views

0 votes

0 answers

4

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 Active (3.1k points) | 40 views

0 votes

1 answer

5

#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 Loyal (8.3k points) | 101 views

0 votes

1 answer

6

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

asked Sep 26, 2017 in Compiler Design by saxena0612 Boss (11.8k points) | 100 views

0 votes

3 answers

7

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 Loyal (7.2k points) | 130 views

+1 vote

1 answer

8

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 (113 points) | 81 views

0 votes

1 answer

9

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 (67 points) | 122 views

+1 vote

0 answers

10

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 4, 2016 in Theory of Computation by makhdoom ghaya Boss (30.2k points) | 222 views

+3 votes

2 answers

11

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 Veteran (105k points) | 712 views

+1 vote

3 answers

12

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 22, 2016 in Theory of Computation by makhdoom ghaya Boss (30.2k points) | 324 views

+3 votes

1 answer

13

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 Others by jothee Veteran (105k points) | 664 views

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 questions tagged context-free-grammars

Recent Posts

Recent Blog Comments