retagged by
690 views

1 Answer

Best answer
3 votes
3 votes
Only $L_2$ and $L_4$ are CFL because there is only one comparison at one time and CFL can do one comparison.

$L_2 =  i \leq j \text{ or } j \leq i$. So,  there is no relation between $i$ and $j$, and they can be anything. (The condition becomes trivial as any $i$ and $j$ satisfies it). Thus, we can read all the $a$'s without pushing into stack. To ensure that $j=k$, push all $b$s into stack. When we encounter $c$'s pop all $b$'s one by one. Thus, it is a DCFL.

$L_4$: $i=j$ can be checked by pushing for $a$'s and popping for $b$'s. If at the end of popping for $b$'s, we end up with an empty stack, we need to check that $c$'s are even, which can be accomplished by a D-PDA. If we end up on a non-empty stack, we accept. Thus, $L_4$ is also a DCFL.

Related questions

357
views
0 answers
1 votes
616
views
1 answers
1 votes
Zeal asked Dec 13, 2015
616 views
To prove that language $L$ is not regular, we may show that $L$ is the intersection of two regular languages.$L$ is the intersection of two non-regular languages.the unio...
657
views
2 answers
0 votes
pC asked Nov 17, 2015
657 views
Consider the language$L_1 = \{a^n b^{2n} \mid n\geq 1 \},$and the homomorphism $h(p)=a, h(q)=aa.$Let $L_2= h^{-1} (L_1)$ and $R= p^*q^*.$Choose the false statement$L_2 \c...
596
views
0 answers
0 votes
pC asked Sep 7, 2018
596 views
#include <stdio.h>int main(void) { int i=10; printf(" %d %d %d",i==10,i=40,i>15 );} Conceptsundefined behaviorfloating point representation