389 views
1 votes
1 votes
1)  $L_1=\{a^{n+m}b^nc^m \:|\: n,m\geq1\}$ is regular?

2)$L_2=\{a^nb^{3^n} \:|\: n\geq1\}$  is CFL?

please help with an explanation

2 Answers

0 votes
0 votes
Hello there!

Regular Languages : Cant Remember anything except the state they are in.

Since there is a relation between m and n , that needs to be stored somewhere. Hence it is not regular.

ii) it is not cfl , cannot  be implemented with stack . ( Read the question wrong)
edited by
0 votes
0 votes

1. am+nbncm . it is not Regular.
it is CFL.
we can rewrite am+nbncas amanbncm

am depends on cand an depends on bn

So it is not Regular

PDA Design
1. Push all 'a' into Stack.
2. Pop 1 'a' for 1 'b'.

3. Pop 1 'a' for 1'c'.
If String is empty and Stack is also empty, String is accepted.

2.anb3^n n>=1
it is not regular not also not CFL.


 

edited by

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
151 views
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.