Register

Peter Linz Edition 5 Exercise 8.1 Question 7(j) (Page No. 212)

345 views
0 votes
0 votes
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}\}$.
User Avatar

1 Answer

0 votes
0 votes

This one is not CFL as we need to implement two stacks to eastablish the relation between a-b and m-n..

Clearly not possible in CFL. 

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Rishi yadav asked Apr 15, 2019
363 views
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}\}$.
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 ...
User Avatar
0 votes
0 votes
0 answers
2
Rishi yadav asked Apr 15, 2019
193 views
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}\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prim...
User Avatar
0 votes
0 votes
0 answers
3
Rishi yadav asked Apr 15, 2019
292 views
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)\}$.
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)\...
User Avatar
0 votes
0 votes
0 answers
4
Rishi yadav asked Apr 15, 2019
172 views
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)\}$.
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...
User Avatar
Link Copied!