Recent questions tagged context-free-language

+1 vote

0 answers

1

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 Boss (46.5k points) | 45 views

+1 vote

0 answers

2

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 (418k points) | 41 views

0 votes

0 answers

3

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 (14k points) | 52 views

0 votes

0 answers

4

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 (14k points) | 34 views

0 votes

1 answer

5

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 (14k points) | 43 views

+1 vote

1 answer

6

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) | 42 views

0 votes

1 answer

7

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.4k points) | 59 views

0 votes

1 answer

8

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.4k points) | 45 views

+1 vote

0 answers

9

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 (399 points) | 113 views

0 votes

0 answers

10

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 (14k points) | 25 views

0 votes

0 answers

11

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) | 40 views

0 votes

0 answers

12

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) | 40 views

0 votes

0 answers

13

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) | 21 views

0 votes

0 answers

14

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) | 25 views

0 votes

0 answers

15

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) | 7 views

0 votes

0 answers

16

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) | 27 views

0 votes

0 answers

17

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) | 14 views

0 votes

0 answers

18

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) | 6 views

0 votes

0 answers

19

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) | 23 views

0 votes

0 answers

20

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) | 21 views

0 votes

0 answers

21

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) | 26 views

0 votes

0 answers

22

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) | 23 views

0 votes

0 answers

23

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) | 13 views

0 votes

0 answers

24

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

0 votes

0 answers

25

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

0 votes

0 answers

26

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

0 votes

0 answers

27

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

0 votes

0 answers

28

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

0 votes

0 answers

29

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

0 votes

0 answers

30

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