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

41 votes

1 answer

601

GATE CSE 2010 | Question: 40
Consider the languages $L1=\{0^i1^j\ \mid i \neq j\}, $ $L2=\{0^i1^j\mid i=j\},$ $L3=\{0^i1^j \mid i=2j+1\},$ $L4=\{0^i1^j \mid i\neq2j\}$ Only $L2$ is context free. Only $L2$ and $L3$ are context free. Only $L1$ and $L2$ are context free. All are context free

Consider the languages$L1=\{0^i1^j\ \mid i \neq j\}, $$L2=\{0^i1^j\mid i=j\},$$L3=\{0^i1^j \mid i=2j+1\},$$L4=\{0^i1^j \mid i\neq2j\}$Only $L2$ is context free.Only $L2$ ...

go_editor

12.0k views

go_editor asked Sep 30, 2014

32 votes

2 answers

602

GATE CSE 2014 Set 3 | Question: 36
Consider the following languages over the alphabet $\sum = \{0, 1, c\}$ $L_1 = \left\{0^n1^n\mid n \geq 0\right\}$ $L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$ ... the string $w$. Which of these languages are deterministic Context-free languages? None of the languages Only $L_1$ Only $L_1$ and $L_2$ All the three languages

Consider the following languages over the alphabet $\sum = \{0, 1, c\}$$L_1 = \left\{0^n1^n\mid n \geq 0\right\}$$L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$$L_3 = ...

go_editor

10.0k views

go_editor asked Sep 28, 2014

32 votes

3 answers

603

GATE CSE 2014 Set 3 | Question: 35
Which one of the following problems is undecidable? Deciding if a given context-free grammar is ambiguous. Deciding if a given string is generated by a given context-free grammar. Deciding if the language generated by a given context-free grammar is empty. Deciding if the language generated by a given context-free grammar is finite.

Which one of the following problems is undecidable?Deciding if a given context-free grammar is ambiguous.Deciding if a given string is generated by a given context-free g...

go_editor

8.8k views

go_editor asked Sep 28, 2014

34 votes

2 answers

604

GATE CSE 1999 | Question: 7
Show that the language $L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$ is not context free. $c$ is not $0$ or $1$.

Show that the language $$L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$$ is not context free. $c$ is not $0$ or $1$.

Kathleen

5.2k views

Kathleen asked Sep 23, 2014

20 votes

3 answers

605

GATE CSE 1999 | Question: 1.5
Context-free languages are closed under: Union, intersection Union, Kleene closure Intersection, complement Complement, Kleene closure

Context-free languages are closed under:Union, intersectionUnion, Kleene closureIntersection, complementComplement, Kleene closure

Kathleen

7.5k views

Kathleen asked Sep 23, 2014

36 votes

5 answers

606

GATE CSE 2005 | Question: 57
Consider the languages: $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$ $L_2 = \left\{w\text{#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{#}$ ... of the following is TRUE? $L_1$ is a deterministic CFL $L_2$ is a deterministic CFL $L_3$ is a CFL, but not a deterministic CFL $L_3$ is a deterministic CFL

Consider the languages:$L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$$L_2 = \left\{w\text{#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{#}$ is a special symbol$...

Kathleen

8.6k views

Kathleen asked Sep 22, 2014

34 votes

7 answers

607

GATE CSE 2009 | Question: 12, ISRO2016-37
$S \to 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

$$S \to aSa \mid bSb\mid a\mid b$$The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of:all palindromesall odd length palindromesstrings t...

Kathleen

20.7k views

Kathleen asked Sep 22, 2014

51 votes

6 answers

608

GATE CSE 2006 | Question: 19
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? $L_1$ only $L_3$ only $L_1$ and $L_2$ $L_2$ and $L_3$

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 c...

Rucha Shelke

15.6k views

Rucha Shelke asked Sep 17, 2014

64 votes

4 answers

609

GATE CSE 2003 | Question: 51
Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$ Which of the following statements is true? $G$ is not ambiguous There ... $L(G)$ We can find a deterministic finite state automaton that accepts $L(G)$

Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$Which of the following...

Kathleen

17.7k views

Kathleen asked Sep 17, 2014

30 votes

3 answers

610

GATE CSE 2001 | Question: 1.5
Which of the following statements is true? If a language is context free it can always be accepted by a deterministic push-down automaton The union of two context free languages is context free The intersection of two context free languages is a context free The complement of a context free language is a context free

Which of the following statements is true?If a language is context free it can always be accepted by a deterministic push-down automatonThe union of two context free lang...

Kathleen

14.0k views

Kathleen asked Sep 14, 2014

27 votes

2 answers

611

GATE CSE 2000 | Question: 7
Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the substring $00$ nor the substring $11$. Consider the grammar $S \to aSAb $ $S \to \epsilon $ $A \to bA $ $ A \to \epsilon $ where $S$ ... $i, j \geq 0$, where $i$ and $j$ satisfy some condition. What is the condition on the values of $i$ and $j$?

Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the substring $00$ nor the substring $11$.Conside...

Kathleen

4.8k views

Kathleen asked Sep 14, 2014

23 votes

4 answers

612

GATE CSE 1992 | Question: 02,xix
Context-free languages are: closed under union closed under complementation closed under intersection closed under Kleene closure

Context-free languages are:closed under unionclosed under complementationclosed under intersectionclosed under Kleene closure

Kathleen

5.0k views

Kathleen asked Sep 13, 2014

5 votes

2 answers

613

Which of the following languages are CFL?
Which of the following languages are CFL? $L_1= \left \{ 0^n 1^m \mid n \leq m \leq 2n \right \} \\[1em] L_2 =\left \{ a^i b^j c^k \mid i=2j \text{ or } j=2k \right \}$

Which of the following languages are CFL?$$L_1= \left \{ 0^n 1^m \mid n \leq m \leq 2n \right \} \\[1em] L_2 =\left \{ a^i b^j c^k \mid i=2j \text{ or } j=2k \right \}$$

gatecse

2.0k views

gatecse asked Sep 12, 2014

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