recategorized by
4,045 views
2 votes
2 votes

Which of the following statements is true?

  1. The union of two context free languages is context free
  2. The intersection of two context free languages is context free
  3. The complement of a context free language is context free
  4. If a language is context free, it can always be accepted by a deterministic pushdown automaton
recategorized by

2 Answers

1 votes
1 votes
context free languages are  not closed under complementation and intersection so option B and C are false

all CFL are accepted by Push down automaton but only DCFL are accepted  deterministic pushdown automaton

so D is also false

context free languages are  closed under union operation hence  option A is true
0 votes
0 votes

Context-free languages are closed under −

  • Union
  • Concatenation
  • Kleene Star operation

Therefore Option A is true let check other option also

Context-free languages are not closed under −

  • Intersection − If L1 and L2 are context free languages, then L1 ∩ L2 is not necessarily context free.

  • Intersection with Regular Language − If L1 is a regular language and L2 is a context free language, then L1 ∩ L2 is a context free language.

  • Complement − If L1 is a context free language, then L1’ may not be context free.

B and C are false now let see D

As DPDA accept only DCFL not all CFL therefore D is also false

therefore Option A is correct

Answer:

Related questions