Recent questions tagged context-free-language

+1 vote

0 answers

1

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 (235 points) | 68 views

0 votes

0 answers

2

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 (11.7k points) | 21 views

0 votes

0 answers

3

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 (11k points) | 26 views

0 votes

0 answers

4

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 (11k points) | 24 views

0 votes

0 answers

5

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 (11k points) | 17 views

0 votes

0 answers

6

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 (11k points) | 24 views

0 votes

0 answers

7

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 (11k points) | 6 views

0 votes

0 answers

8

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 (11k points) | 12 views

0 votes

0 answers

9

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 (11k points) | 13 views

0 votes

0 answers

10

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 (11k points) | 5 views

0 votes

0 answers

11

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 (11k points) | 22 views

0 votes

0 answers

12

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 (11k points) | 19 views

0 votes

0 answers

13

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 (11k points) | 23 views

0 votes

0 answers

14

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 (11k points) | 22 views

0 votes

0 answers

15

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 (11k points) | 12 views

0 votes

0 answers

16

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 (11.7k points) | 3 views

0 votes

0 answers

17

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 (11.7k points) | 3 views

0 votes

0 answers

18

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 (11.7k points) | 5 views

0 votes

0 answers

19

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 (11.7k points) | 10 views

0 votes

0 answers

20

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 (11.7k points) | 3 views

0 votes

0 answers

21

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 (11.7k points) | 8 views

0 votes

0 answers

22

Peter Linz Edition 4 Exercise 5.1 Question 15 (Page No. 134)
Show that the following language is context-free. $L=$ {$uvwv^R:u,v,w∈$ {$a,b$}$^+,|u|=|w|=2$}.

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

0 votes

0 answers

23

Peter Linz Edition 4 Exercise 5.1 Question 14 (Page No. 134)
Let $L_1$ be the language $L_1 =$ {$a^nb^mc^k : n = m$ or $m ≤ k$} and $L_2$ the language $L_2 =$ {$a^nb^mc^k : n + 2m = k$}. Show that $L_1 ∪ L_2$ is a context-free language.

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

0 votes

0 answers

24

Peter Linz Edition 4 Exercise 5.1 Question 9 (Page No. 134)
Show that $L =$ {$w ∈$ {$a,b,c$}$^* : |w| = 3n_a(w)$} is a context-free language.

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

0 votes

0 answers

25

Peter Linz Edition 4 Exercise 5.1 Question 8 (Page No. 134)
Find context-free grammars for the following languages (with $n ≥ 0, m ≥ 0, k ≥ 0$). (a) $L =$ {$a^nb^mc^k : n = m$ or $m ≤ k$}. (b) $L =$ {$a^nb^mc^k : n = m$ or $m ≠ k$}. (c) $L =$ {$a^nb^mc^k : k = n + m$}. (d) $L =$ ... $L =$ {$a^nb^mc^k, k ≠ n + m$}. (h) $L =$ {$a^nb^mc^k : k ≥ 3$}.

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

0 votes

0 answers

26

Peter Linz Edition 4 Exercise 5.1 Question 7 (Page No. 133)
Find context-free grammars for the following languages (with $n ≥ 0, m ≥ 0$). (a) $L =$ {$a^nb^m : n ≤ m + 3$}. (b) $L =$ {$a^nb^m : n ≠ m − 1$ ... $v$ is any prefix of $w$}. (g) $L =$ {$w ∈$ {$a,b$}$^* : n_a (w) = 2n_b(w) + 1$}.

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

0 votes

1 answer

27

CFG Doubt
what is the CFG for the language L=w where number of a’s in w+number of b’s in w=number of c’s in w how to approach this?

asked Mar 7 in Theory of Computation by aditi19 Active (3.4k points) | 119 views

0 votes

1 answer

28

CFG Doubt
S->A | B A→ ε B->aBb B->b what is the complement of the language of this grammar?

asked Mar 2 in Theory of Computation by aditi19 Active (3.4k points) | 113 views

0 votes

1 answer

29

Peter Linz Edition 4 Exercise 5.1 Question 13.a (Page No. 134)
L={$a^nb^n | n\geq 0$} please show how $L^2$ is CFL

asked Mar 1 in Theory of Computation by aditi19 Active (3.4k points) | 115 views

0 votes

3 answers

30

GATE2019-31
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free? $\{ww^R \mid w \in \{a, b\}^*\}$ $\{wa^nb^nw^R \mid w \in \{a,b\}^*, n \geq 0\}$ $\{wa^nw^Rb^n \mid w \in \{a,b\}^* , n \geq 0\}$ $\{ a^nb^i \mid i \in \{n, 3n, 5n\}, n \geq 0\}$

asked Feb 7 in Theory of Computation by Arjun Veteran (399k points) | 1.7k 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-language

Recent Posts

Recent Blog Comments