Recent questions tagged context-free-grammar / GATE Overflow for GATE CSE

1 votes

1 answer

31

PhD Qualifier Examination, Paper I
Give a context-free grammar for the set of all strings over the alphabet {a, b} with exactly twice as many a’s as b’s. Explain the working of the grammar by characterizing the strings generated by each non-terminal.

Give a context-free grammar for the set of all strings over the alphabet {a, b} with exactly twice as many a’s as b’s. Explain the working of the grammar by character...

rsansiya111

272 views

rsansiya111 asked Sep 17, 2022

0 votes

0 answers

32

PDA | TOC | Practice Question
Identify the type of the given language and draw the corresponding automata for the language. $L=\left \{a^{i}b^{j}c^{k} \space\ | \space\ j=max(i,k) \right \}$ A] Regular B] DCFL C] CFL but not DCFL D] Non-CFL Please describe your selection.

Identify the type of the given language and draw the corresponding automata for the language.$L=\left \{a^{i}b^{j}c^{k} \space\ | \space\ j=max(i,k) \right \}$A] RegularB...

anupamsworld

539 views

anupamsworld asked Sep 2, 2022

0 votes

1 answer

33

Construct a grammar which generates all odd integers up to 999

clendaya

269 views

clendaya asked Aug 11, 2022

0 votes

2 answers

34

made easy test series - parsing - context-free grammar
Consider the following context-free grammar: Find the number of unique productions in {Goto (A → D.BC, B) U Goto (A → .DBC, D)}

Consider the following context-free grammar:Find the number of unique productions in {Goto (A → D.BC, B) U Goto (A → .DBC, D)}

atulcse

898 views

atulcse asked Jan 16, 2022

3 votes

2 answers

35

#Gate CS Applied Course Mock Test
Is this Language a CFL? If yes, Can you please explain the implementation.

Is this Language a CFL?If yes, Can you please explain the implementation.

Rajesh Reddy

619 views

Rajesh Reddy asked Jan 3, 2022

1 votes

1 answer

36

Test series Made easy
How to solve this ? Please help.

How to solve this ? Please help.

raja11sep

656 views

raja11sep asked Dec 31, 2021

1 votes

1 answer

37

made easy test 1 2022
how option 2 is correct becz regular lang. dosnt accept comparision can anyone explain?

how option 2 is correct becz regular lang. dosnt accept comparision can anyone explain?

jugnu1337

236 views

jugnu1337 asked Dec 16, 2021

2 votes

1 answer

38

Greibach Normal Form
Convert the following grammar into Greibach Normal Form. E-> E + T | T T-> T*F | F F->(E) | a I am unable to process this type of grammer into GNF, Can someone please provide a detailed explaination?

Convert the following grammar into Greibach Normal Form.E- E + T | TT- T*F | FF->(E) | a I am unable to process this type of grammer into GNF, Can someone please provide ...

hustlerrr

4.7k views

hustlerrr asked Nov 17, 2021

3 votes

1 answer

39

Applied Test Series
How to approach with such questions. Do we have to generate strings to validate the property of the grammars ?

How to approach with such questions. Do we have to generate strings to validate the property of the grammars ?

LRU

365 views

LRU asked Oct 3, 2021

1 votes

2 answers

40

can someone share the approach for the following que
14.Show that the grammar S → aSb |SS| e is ambiguous, but that the language denoted by it is not. Can someone share the approach for second part.

14.Show that the grammar S → aSb |SS| e is ambiguous, but that the language denoted by it is not.Can someone share the approach for second part.

mk_007

268 views

mk_007 asked Oct 2, 2021

2 votes

1 answer

41

TIFR CSE 2021 | Part B | Question: 9
Let $L$ be a context-free language generated by the context-free grammar $G = (V, \Sigma, R, S)$ where $V$ is the finite set of variables, $\Sigma$ the finite set of terminals (disjoints from $V$), $R$ the finite set of rules and $S \in V$ the start variable. ... ${L}'=L^{\ast }$ ${L}'=\left \{ xx \mid x \in L \right \}$ None of the above

Let $L$ be a context-free language generated by the context-free grammar $G = (V, \Sigma, R, S)$ where $V$ is the finite set of variables, $\Sigma$ the finite set of term...

soujanyareddy13

668 views

soujanyareddy13 asked Mar 25, 2021

3 votes

1 answer

42

GATE Overflow Test Series | Mock GATE | Test 1 | Question: 41
Which of the given strings is/are NOT generated by the below context-free grammar? $S$ is the start symbol and the set of non-terminal symbols is $\{a,b\}.$ The production rules are: $S \rightarrow bS \mid aAaS \mid \varepsilon$ $A \rightarrow bA \mid \varepsilon$ $abababbbb$ $aaaaaaaaa$ $bbbbabbbb$ $aaaabaaaa$

Which of the given strings is/are NOT generated by the below context-free grammar? $S$ is the start symbol and the set of non-terminal symbols is $\{a,b\}.$The production...

gatecse

220 views

gatecse asked Jan 3, 2021

1 votes

2 answers

43

GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 4
A context-free grammar $G$ is ambiguous if and only if some string $w \in L(G)$ has different leftmost and rightmost derivations. some string $w \in L(G)$ has at least two different parse trees. every string $w \in L(G)$ has at least two different parse trees. some string $w \in L(G)$ has at least two different leftmost derivations.

A context-free grammar $G$ is ambiguous if and only ifsome string $w \in L(G)$ has different leftmost and rightmost derivations.some string $w \in L(G)$ has at least two ...

gatecse

112 views

gatecse asked Oct 15, 2020

2 votes

1 answer

44

GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 16
A derivation of a string $w$ of length $n$ in a context-free grammar in Chomsky normal form must involve exactly $2n-1$ applications of rules for all $n> 0$ must involve at least $2n$ ... arbitrarily large number. must involve at least $n$ rules and at most $2n$ rules for all $n > 0$.

A derivation of a string $w$ of length $n$ in a context-free grammar in Chomsky normal formmust involve exactly $2n-1$ applications of rules for all $n 0$must involve at ...

gatecse

191 views

gatecse asked Sep 29, 2020

3 votes

1 answer

45

GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 22
Which of the following are context-free grammar for the language that contains all strings (including empty string) with matched parenthesis? $S \rightarrow (\; )$ $S \rightarrow SS$ $S \rightarrow (S)$ ... $S \rightarrow \varepsilon$ $S \rightarrow (S )$ $S \rightarrow SS$ $S \rightarrow \varepsilon$

Which of the following are context-free grammar for the language that contains all strings (including empty string) with matched parenthesis?$S \rightarrow (\; )$$S \righ...

gatecse

234 views

gatecse asked Sep 29, 2020

1 votes

1 answer

46

GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 23
What does the following context-free grammar describe? $S$ is the start symbol and the set of nonterminal symbols is $\{a,b\}.$ The production rules are: $S \rightarrow a$ $S \rightarrow aS$ $S \rightarrow bS$ Strings ... that have an equal number of $b's$ and $a's$ Strings that have an odd number of $b's$

What does the following context-free grammar describe?$S$ is the start symbol and the set of nonterminal symbols is $\{a,b\}.$ The production rules are:$S \rightarrow a$$...

gatecse

82 views

gatecse asked Sep 29, 2020

0 votes

1 answer

47

NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 10
Consider an $\varepsilon$-tree CFG. If for every pair of productions $A\rightarrow u$ and $A\rightarrow v$ If $\text{FIRST(u)} \cap \text{FIRST(v)}$ is empty then the CFG has to be $LL(1).$ If the CFG is $LL(1)$ then $\text{FIRST(u)} \cap \text{FIRST(v)}$ has to be empty. Both $(A)$ and $(B)$ None of the above

Consider an $\varepsilon$-tree CFG. If for every pair of productions $A\rightarrow u$ and $A\rightarrow v$If $\text{FIRST(u)} \cap \text{FIRST(v)}$ is empty then the CFG ...

admin

3.2k views

admin asked Apr 1, 2020

0 votes

1 answer

48

NIELIT 2016 MAR Scientist B - Section C: 29
The CFG $S \to aS\mid bS\mid a\mid b$ is equivalent to $(a+b)$ $(a+b)(a+b)^*$ $(a+b)(a+b)$ all of these

The CFG $S \to aS\mid bS\mid a\mid b$ is equivalent to $(a+b)$$(a+b)(a+b)^*$$(a+b)(a+b)$all of these

admin

1.4k views

admin asked Mar 31, 2020

0 votes

1 answer

49

NIELIT 2017 DEC Scientist B - Section B: 7
Let $G$ be a grammar in CFG and let $W_1,W_2\in L(G)$ such that $\mid W_1\mid=\mid W_2\mid$ then which of the following statements is true? Any derivation of $W_1$ has exactly the same number of steps as any derivation ... $W_1$ may be shorter than the derivation of $W_2$ None of the options

Let $G$ be a grammar in CFG and let $W_1,W_2\in L(G)$ such that $\mid W_1\mid=\mid W_2\mid$ then which of the following statements is true?Any derivation of $W_1$ has exa...

admin

1.1k views

admin asked Mar 30, 2020

0 votes

1 answer

50

NIELIT 2017 DEC Scientist B - Section B: 26
The grammar $S\rightarrow aSb\mid bSa\mid SS\mid \varepsilon $ is: Unambiguous CFG Ambiguous CFG Not a CFG Deterministic CFG

The grammar $S\rightarrow aSb\mid bSa\mid SS\mid \varepsilon $ is:Unambiguous CFGAmbiguous CFGNot a CFGDeterministic CFG

admin

1.2k views

admin asked Mar 30, 2020

0 votes

2 answers

51

UGC NET CSE | December 2005 | Part 2 | Question: 4
Which sentence can be generated by $S\rightarrow d/bA, A\rightarrow d/ccA$ : $\text{bccddd}$ $\text{aabccd}$ $\text{ababccd}$ $\text{abbbd}$

Which sentence can be generated by $S\rightarrow d/bA, A\rightarrow d/ccA$ :$\text{bccddd}$$\text{aabccd}$$\text{ababccd}$$\text{abbbd}$

go_editor

417 views

go_editor asked Mar 27, 2020

0 votes

2 answers

52

UGC NET CSE | January 2017 | Part 3 | Question: 22
Let $G= (V,T,S,P)$ be a context-free grammer such that every one of its productions is of the form $A\rightarrow v$, with $\mid v \mid=K> 1$. The derivation tree for any $W \in L(G)$ has a height $h$ ... $\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid - 1}{K-1} \right)$

Let $G= (V,T,S,P)$ be a context-free grammer such that every one of its productions is of the form $A\rightarrow v$, with $\mid v \mid=K 1$. The derivation tree for any ...

go_editor

1.4k views

go_editor asked Mar 24, 2020

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