Recent questions tagged context-free-language - GATE Overflow

+1 vote

1 answer

1

CMI2019-A-1
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$ The language $L_{1}\cup L_{2}$ is: regular, but not context-free context-free, but not regular both regular and context-free neither regular nor context-free

asked Sep 13 in Theory of Computation by gatecse Boss (16.6k points) | 88 views

+1 vote

0 answers

2

Ullman (TOC) Edition 3 Exercise 9.5 Question 3 (Page No. 418 - 419)
It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but that is not the same thing. To prove our initial ... Ogden's lemma to force equality in the lengths of certain substrings as in the hint to Exercise $7.2.5(b)$.

asked Jul 26 in Theory of Computation by Lakshman Patel RJIT Veteran (53.4k points) | 82 views

+1 vote

0 answers

3

UGCNET-June-2019-II-77
How can the decision algorithm be constructed for deciding whether context-free language $L$ is finite? By constructing redundant CFG G in CNF generating language $\underline{L}$ By constructing non-redundant CFG G in CNF generating language $L$ By constructing non-redundant CFG ... stands for null) Which of the following is correct? a only b only c only None of a, b and c

asked Jul 2 in Theory of Computation by Arjun Veteran (423k points) | 92 views

+1 vote

0 answers

4

Peter Linz Edition 4 Exercise 8.1 Question 8 (Page No. 212)
Determine whether or not the following languages are context-free. (a) $L=$ {$a^nww^Ra^n : n ≥ 0, w ∈$ {$a,b$}*} (b) $L=$ {$a^nb^ja^nb^j : n ≥ 0, j ≥ 0$}. (C) $L=$ {$a^nb^ja^jb^n : n ≥ 0, j ≥ 0$}. (d) $L=$ {$a^nb^ja^kb^l : n + j ≤ k + l$ ... $ L=$ {$a^nb^nc^j : n ≤j$}. (g) $L=$ {$w ∈$ {$a, b, c$}* $: n_a(w)= n_b (w)=2n_c(w)$}.

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 71 views

+1 vote

0 answers

5

Peter Linz Edition 4 Exercise 8.1 Question 5 (Page No. 212)
Is the language L = {$a^nb^m : n = 2^m$} context-free?

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 48 views

0 votes

1 answer

6

Peter Linz Edition 4 Exercise 8.1 Question 1 (Page No. 212)
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 51 views

+1 vote

1 answer

7

Theory of Computation: Context Free Languages
Hi, I am having a doubt understanding the result of CFL - Regular: Here's my approach: CFL - Regular = CFL INTERSECTION Regular' = CFL INTERSECTION Regular = CFL Suppose some CFL L1= {a^n b^n | n>=1} and some Regular R1= (a+b)* ... to say CFL - Regular = Regular or CFL - Regular = CFL ? If both are separate options, which one should I go for? Thanks

asked Jun 9 in Theory of Computation by DukeThunders (39 points) | 50 views

0 votes

1 answer

8

ACE Academy: Recognition of CFG
$L1 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{or} \left ( n = p \right ) \right \}$ $L2 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{and} \left ( n = p \right ) \right \}$ $(a)$ Both are NCFL’s $(b)$ L1 is DCFL and L2 is NCFL $(c)$ L1 is NCFL and L2 is not context-free $(d)$ Both are not context-free

asked May 23 in Theory of Computation by Hirak Active (3.5k points) | 74 views

0 votes

1 answer

9

self doubt: TOC
is union of regular language and context free language always regular?

asked May 22 in Theory of Computation by Hirak Active (3.5k points) | 52 views

+1 vote

0 answers

10

Self Doubt : Ambiguity
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?

asked May 10 in Theory of Computation by logan1x Junior (803 points) | 119 views

0 votes

0 answers

11

Peter Linz Edition 4 Exercise 6.1 Question 5 (Page No. 161)
Eliminate all useless productions from the grammar $S\rightarrow aS|AB,$ $A\rightarrow bA,$ $B\rightarrow AA.$ What language does this grammar generate?

asked Apr 15 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 28 views

0 votes

0 answers

12

Peter Linz Edition 5 Exercise 8.1 Question 7(k) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n is prime and m is not prime}\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 41 views

0 votes

0 answers

13

Peter Linz Edition 5 Exercise 8.1 Question 7(j) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m:\text{n is prime or m is prime}\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 40 views

0 votes

0 answers

14

Peter Linz Edition 5 Exercise 8.1 Question 7(i) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prime}\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 21 views

0 votes

0 answers

15

Peter Linz Edition 5 Exercise 8.1 Question 7(h) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 25 views

0 votes

0 answers

16

Peter Linz Edition 5 Exercise 8.1 Question 7(g) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w)\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 7 views

0 votes

0 answers

17

Peter Linz Edition 5 Exercise 8.1 Question 7(f) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w:n_a(w) <n_b(w)<n_c(w)\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 29 views

0 votes

0 answers

18

Peter Linz Edition 5 Exercise 8.1 Question 7(e) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 18 views

0 votes

0 answers

19

Peter Linz Edition 5 Exercise 8.1 Question 7(d) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 6 views

0 votes

0 answers

20

Peter Linz Edition 5 Exercise 8.1 Question 7(c) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^jc^k:k=jn\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 24 views

0 votes

0 answers

21

Peter Linz Edition 5 Exercise 8.1 Question 7(b) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j: n\geq(j-1)^3\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 21 views

+1 vote

0 answers

22

Peter Linz Edition 5 Exercise 8.1 Question 7(a) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j : n\leq j^2\}$.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 28 views

0 votes

0 answers

23

Peter Linz Edition 5 Exercise 8.1 Question 6 (Page No. 212)
Show that the language $L = \Big\{ a^{n^2} :n\geq 0\Big\}$ is not context free.

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 23 views

0 votes

0 answers

24

Peter Linz Edition 5 Exercise 8.1 Question 5 (Page No. 212)
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$

asked Apr 15 in Theory of Computation by Rishi yadav Boss (11.3k points) | 13 views

0 votes

0 answers

25

Peter Linz Edition 4 Exercise 5.1 Question 26 (Page No. 135)
Find a linear grammar for the language $L=$ {$a^nb^m:n\neq m$}.

asked Apr 14 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 4 views

0 votes

0 answers

26

Peter Linz Edition 4 Exercise 5.1 Question 25 (Page No. 135)
Prove that if $G$ is a context-free grammar, then every $w ∈ L(G)$ has a leftmost and rightmost derivation. Give an algorithm for finding such derivations from a derivation tree.

asked Apr 14 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 4 views

0 votes

0 answers

27

Peter Linz Edition 4 Exercise 5.1 Question 19 (Page No. 134)
Show a derivation tree for the string $aabbbb$ with the grammar $S\rightarrow AB|\lambda,$ $A\rightarrow aB,$ $B\rightarrow Sb.$ Give a verbal description of the language generated by this grammar.

asked Apr 14 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 7 views

0 votes

0 answers

28

Peter Linz Edition 4 Exercise 5.1 Question 18 (Page No. 134)
Show that the language $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^+,w_1\neq w_2^R$}, with $Σ =$ {$a,b,c$},is context-free.

asked Apr 14 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 13 views

0 votes

0 answers

29

Peter Linz Edition 4 Exercise 5.1 Question 17 (Page No. 134)
Show that the complement of the language $L =$ {$a^nb^mc^k : k = n + m$} is context-free.

asked Apr 14 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 6 views

0 votes

0 answers

30

Peter Linz Edition 4 Exercise 5.1 Question 16 (Page No. 134)
Show that the complement of the language $L=$ {$ww^R:w∈$ {$a,b$}$^*$} is context-free.

asked Apr 14 in Theory of Computation by Naveen Kumar 3 Boss (15.1k points) | 11 views

Page:

1
2
3
4
5
6
...
13
next »

Recent questions tagged context-free-language

50,650 questions

56,185 answers

193,937 comments

94,684 users