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

1 votes

1 answer

61

identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b}
identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b} if yes then why please explain

identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b}if yes then why please explain

sachin_27

1.3k views

sachin_27 asked Jun 1, 2022

1 votes

0 answers

62

Self Doubt about Construction of CFG
I am trying to construct a CFG for this following langauge: L = $\{0^i 1^j | i \neq j \ and \ i, j > 0\}$, this is what I came up with: $ S \rightarrow A \ | \ B $ $A \rightarrow 0A1 \ |\ A1 \ |\ 011$ ... strings that we can have: s = {011, 00111, 001, 00011, ...} and it worked. So, my question is, is this correct CFG for this particular L?

I am trying to construct a CFG for this following langauge: L = $\{0^i 1^j | i \neq j \ and \ i, j 0\}$, this is what I came up with:$ S \rightarrow A \ | \ B $$A \righ...

HenryAsks21

321 views

HenryAsks21 asked Apr 30, 2022

24 votes

2 answers

63

GATE CSE 2022 | Question: 37
Consider the following languages: $L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}$ $L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| > 0 \}$ Note that $w^{R}$ is the reversal of the string $w.$ Which of the following is/are ... $L_{2}$ are context-free. $L_{1}$ is regular and $L_{2}$ is context-free. $L_{1}$ and $L_{2}$ are context-free but not regular.

Consider the following languages:$L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}$$L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| 0 \}$Note that $w^{R}$ is the reve...

Arjun

7.2k views

Arjun asked Feb 15, 2022

20 votes

2 answers

64

GATE CSE 2022 | Question: 38
Consider the following languages: $L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$ $L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$ $L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$ Which of the following statements is/are $\text{FALSE}?$ ... $L_{2}$ is context-free. $L_{2}, L_{3}$ and $L_{2} \cap L_{3}$ all are context-free. Neither $L_{1}$ nor its complement is context-free.

Consider the following languages:$L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$$L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$$L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$Which ...

Arjun

11.3k views

Arjun asked Feb 15, 2022

1 votes

2 answers

65

DCFL - TOC
Is the following language a DCFL? Please explain your reasoning.

Is the following language a DCFL? Please explain your reasoning.

atulcse

717 views

atulcse asked Jan 21, 2022

0 votes

1 answer

66

parse tree - context-free grammars - TOC
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?

Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?

atulcse

870 views

atulcse asked Jan 21, 2022

0 votes

2 answers

67

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

897 views

atulcse asked Jan 16, 2022

3 votes

2 answers

68

#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

618 views

Rajesh Reddy asked Jan 3, 2022

2 votes

3 answers

69

regular and cfl
if L1 and L2 are not regular language then L1 union L2 is not regular. this statement is true or false? my approach is::: true let suppose L1= a^n b^n AND L2= a^k b^k both are cfl but if we do union then that also be cfl and what happened if union is replaced by concatenation L1 . L2

if L1 and L2 are not regular language then L1 union L2 is not regular.this statement is true or false?my approach is:::true let suppose L1= a^n b^n AND L2= a^k b^kbot...

jugnu1337

1.2k views

jugnu1337 asked Dec 23, 2021

3 votes

3 answers

70

#selfDoubt
complement of CFL can never be CFL. please explain if the above statement is true of false?

complement of CFL can never be CFL.please explain if the above statement is true of false?

BHOJARAM

885 views

BHOJARAM asked Dec 13, 2021

0 votes

1 answer

71

Closure Properties of Languages
let L = “CFL but not REGULAR”, Can we get complement of L as CFL? Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, its complement can never be RE.

let L = “CFL but not REGULAR”, Can we get complement of L as CFL?Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, it...

UltraRadiantX

466 views

UltraRadiantX asked Oct 9, 2021

1 votes

1 answer

72

Applied Test Series
The language accepted by the given PDA is

The language accepted by the given PDA is

LRU

287 views

LRU asked Oct 3, 2021

1 votes

2 answers

73

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

3 answers

74

UGC NET CSE | June 2016 | Part 3 | Question: 56
Let $L=\{0^n1^n|n\ge 0\}$ be a context free language. Which of the following is correct? $\overline L$ is context free and $L^k$ is not context free for any $k\ge1$ $\overline L$ is not context free and $L^k$ ... $L^k$ for any $k\ge1$ are context free Both $\overline L$ and $L^k$ for any $k\ge1$ are not context free

Let $L=\{0^n1^n|n\ge 0\}$ be a context free language. Which of the following is correct?$\overline L$ is context free and $L^k$ is not context free for any $k\ge1$$\overl...

soujanyareddy13

637 views

soujanyareddy13 asked May 10, 2021

1 votes

1 answer

75

TIFR CSE 2021 | Part B | Question: 5
For a language $L$ over the alphabet $\{a, b\}$, let $\overline{L}$ denote the complement of $L$ and let $L^{\ast}$ denote the Kleene-closure of $L$. Consider the following sentences. $\overline{L}$ and $L^{\ast}$ are both context-free. $\overline{L}$ is not ... ? Both (i) and (iii) Only (i) Only (iii) Only (ii) None of the above

For a language $L$ over the alphabet $\{a, b\}$, let $\overline{L}$ denote the complement of $L$ and let $L^{\ast}$ denote the Kleene-closure of $L$. Consider the followi...

soujanyareddy13

676 views

soujanyareddy13 asked Mar 25, 2021

27 votes

2 answers

76

GATE CSE 2021 Set 2 | Question: 41
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$. Which of the following languages is/are context-free? $\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}$ $\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxw^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}$

For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$.Which of the following languages is/are context-free?$\{ wxw^Rx^R \...

Arjun

7.2k views

Arjun asked Feb 18, 2021

11 votes

3 answers

77

GATE CSE 2021 Set 1 | Question: 1
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free? $L_1 \cap L_2$ $L_1 \cdot L_2$ $L_1- L_2$ $L_1\cup L_2$

Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free?$L_1 \cap L_2...

Arjun

7.5k views

Arjun asked Feb 18, 2021

4 votes

1 answer

78

GATE Overflow Test Series | Mock GATE | Test 4 | Question: 65
Mark all the context-free languages given below. (Mark all the appropriate choices) $L = \{x\#w \mid x,w \in \Sigma^* \text{ and } x \text{ is a substring of } w\}$ $L=\{a^nb^{n+m}c^{n+m}d^{n}\mid n,m \geq 0\}$ $L = \{xww_R \mid w \in (a+b)^*,x \in (a+b)^+\}$ $L = \{0^n1^m0^m1^n\mid m,n \geq 0\}$

Mark all the context-free languages given below. (Mark all the appropriate choices)$L = \{x\#w \mid x,w \in \Sigma^* \text{ and } x \text{ is a substring of } w\}$$L=\{a^...

gatecse

438 views

gatecse asked Feb 1, 2021

9 votes

1 answer

79

GATE Overflow Test Series | Mock GATE | Test 2 | Question: 64
Let $D_1$ and $D_2$ be two Deterministic Pushdown Automata. Which of the following problems is/are undecidable? (Mark all the appropriate choices) Is $L(D_1)\cap L(D_2)$ a Deterministic-CFL? Is $L(D_1)\cap L(D_2) = \emptyset?$ Is $L(D_1)\cup L(D_2)$ a Deterministic-CFL? Is $L(D_1)\cup L(D_2)=\sigma^*?$

Let $D_1$ and $D_2$ be two Deterministic Pushdown Automata. Which of the following problems is/are undecidable? (Mark all the appropriate choices)Is $L(D_1)\cap L(D_2)$ a...

gatecse

567 views

gatecse asked Jan 17, 2021

2 votes

2 answers

80

UGC NET CSE | October 2020 | Part 2 | Question: 29
Which of the following statements is true? The union of two context free languages is context free The intersection of two context free languages is context free The complement of a context free language is context free If a language is context free, it can always be accepted by a deterministic pushdown automaton

Which of the following statements is true?The union of two context free languages is context freeThe intersection of two context free languages is context freeThe complem...

go_editor

4.1k views

go_editor asked Nov 20, 2020

8 votes

1 answer

81

GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 19
Mark all the context-free languages given below $L = \{x\#w \mid x,w \in \Sigma^* \text{ and } x \text{ is a substring of } w\}$ $L=\{a^nb^{n+m}c^md^{n}\mid n,m \geq 0\}$ $L = \{1^n \mid n\text{ is a power of }2\}$ $L = \{0^n1^m0^m1^n\mid m,n \geq 0\}$

Mark all the context-free languages given below$L = \{x\#w \mid x,w \in \Sigma^* \text{ and } x \text{ is a substring of } w\}$$L=\{a^nb^{n+m}c^md^{n}\mid n,m \geq 0\}$$L...

gatecse

446 views

gatecse asked Sep 29, 2020

1 votes

1 answer

82

NIELIT 2017 OCT Scientific Assistant A (IT) - Section C: 9
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ Only $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only

Which of the following definitions generates the same languages as $L,$ where$L = \{x^{n}y^{n},n \geq 1\}$$E \rightarrow xEy \mid xy$$xy \mid x^{+}xyy^{+}$$x^{+}y^{+}$ $(...

admin

617 views

admin asked Apr 1, 2020

1 votes

2 answers

83

NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 31
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only

Which of the following definitions generates the same languages as $L,$ where$L = \{x^{n}y^{n},n \geq 1\}$$E \rightarrow xEy \mid xy$$xy \mid x^{+}xyy^{+}$$x^{+}y^{+}$ $(...

admin

626 views

admin asked Apr 1, 2020

2 votes

4 answers

84

NIELIT 2016 MAR Scientist B - Section C: 26
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language? $L_1L_2$ $L_1\cap L_2$ $L_1\cap R$ $L_1\cup L_2$

If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language?$L_1L_2$$L_1\cap L_2$...

admin

934 views

admin asked Mar 31, 2020

2 votes

3 answers

85

NIELIT 2016 DEC Scientist B (CS) - Section B: 3
If $L1$ is CFL and $L2$ is regular language which of the following is false? $L1-L2$ is not Context free $L1$ intersection $L2$ is Context free $\sim L1$ is Context free Both (A) and (C)

If $L1$ is CFL and $L2$ is regular language which of the following is false?$L1-L2$ is not Context free$L1$ intersection $L2$ is Context free$\sim L1$ is Context freeBoth...

admin

768 views

admin asked Mar 31, 2020

2 votes

3 answers

86

NIELIT 2017 DEC Scientist B - Section B: 56
Which of the following statement is true? Deterministic context free language are closed under complement. Deterministic context free language are not closed under Union. Deterministic context free language are closed under intersection with regular set. All of the options

Which of the following statement is true?Deterministic context free language are closed under complement.Deterministic context free language are not closed under Union.De...

admin

1.5k views

admin asked Mar 30, 2020

3 votes

4 answers

87

TIFR CSE 2020 | Part B | Question: 2
Consider the following statements. The intersection of two context-free languages is always context-free The super-set of a context-free languages is never regular The subset of a decidable language is always decidable Let $\Sigma = \{a,b,c\}.$ Let $L\subseteq \Sigma$ be the language of ... Only $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true.

Consider the following statements.The intersection of two context-free languages is always context-freeThe super-set of a context-free languages is never regularThe subse...

admin

1.5k views

admin asked Feb 10, 2020

2 votes

4 answers

88

ISRO2020-37
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure

Context free languages are closed underunion, intersectionunion, kleene closureintersection, complementcomplement, kleene closure

Satbir

2.7k views

Satbir asked Jan 13, 2020

1 votes

0 answers

89

Michael Sipser Edition 3 Exercise 4 Question 31 (Page No. 212)
Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of testing whether $A$ is usable. Formulate this problem as a language and show that it is decidable.

Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of te...

admin

455 views

admin asked Oct 17, 2019

0 votes

0 answers

90

Michael Sipser Edition 3 Exercise 2 Question 58 (Page No. 160)
Let $C = \{ww^{R} \mid w in \{0,1\}^{\ast}\}$. Prove that $C$ is not a DCFL. (Hint: Suppose that when some DPDA $P$ is started in state $q$ with symbol $x$ on the top of its stack, $P$ never pops its ... of $P's$ stack at that point cannot affect its subsequent behavior, so $P's$ subsequent behavior can depend only on $q$ and $x$.)

Let $C = \{ww^{R} \mid w in \{0,1\}^{\ast}\}$. Prove that $C$ is not a DCFL. (Hint: Suppose that when some DPDA $P$ is started in state $q$ with symbol $x$ on the top of ...

admin

197 views

admin asked Oct 12, 2019

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