Recent questions tagged context-free-language

0 votes

0 answers

1

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

0 votes

0 answers

2

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

0 votes

0 answers

3

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

0 votes

1 answer

4

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

+1 vote

1 answer

5

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

0 votes

1 answer

6

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.3k points) | 50 views

0 votes

1 answer

7

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.3k points) | 44 views

+1 vote

0 answers

8

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

0 votes

0 answers

9

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

10

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 (10.6k points) | 36 views

0 votes

0 answers

11

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 (10.6k points) | 38 views

0 votes

0 answers

12

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 (10.6k points) | 20 views

0 votes

0 answers

13

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

0 votes

0 answers

14

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

0 votes

0 answers

15

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 (10.6k points) | 27 views

0 votes

0 answers

16

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

0 votes

0 answers

17

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

0 votes

0 answers

18

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

0 votes

0 answers

19

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

0 votes

0 answers

20

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

0 votes

0 answers

21

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

0 votes

0 answers

22

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

0 votes

0 answers

23

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

24

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

25

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

26

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

0 votes

0 answers

27

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

28

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

29

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

0 votes

0 answers

30

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