in Theory of Computation
693 views
2 votes
2 votes
$a) \{\ 0^i\ 1^j\ 2^k\ \ | where\  i\  \neq  j\  or\  j\ \neq k\  \}$

$b) \{\ 0^i\ 1^j\ 2^k\ \ | where\  i\  \neq  j\  and\  j\ \neq k\  \}$

a) CFL(union of two OR-ed comparisons )

b) CSL( Double comaprison )

Am I correct?
in Theory of Computation
693 views

2 Comments

yes 1 is CFL 2 CSL
1
1
Yes your reasons are also correct.
0
0

1 Answer

0 votes
0 votes
It can be analyse in this way also CFL is not closed under intersection so it takes single comparison means union

CFL closed under intersection  (and) so it takes double comparison

Both are correct

Related questions