recategorized by
1,402 views
0 votes
0 votes

Identify the true statement from the given statements:

  1. A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language.
  2. The complement of a recursive languages is recursive
  3. The complement of a context-free language is context-free
  1. Only $1$
  2. $1$ and $2$
  3. $1$, $2$ and $3$
  4. $2$ and $3$
recategorized by

3 Answers

0 votes
0 votes
1. True

2. True. Recursive Languages are closed under complementation.

3. False. context-free languages are not closed under complementation. Their complement is CSL.

So B is correct.
0 votes
0 votes
TRUE: A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language
TRUE: The complement of a recursive language is recursive
FALSE because The complement of a deterministic context free language is deterministic context free.
Answer:

Related questions

0 votes
0 votes
3 answers
1
Arjun asked Dec 7, 2018
912 views
Consider the following Finite State Automaton. The language accepted by the automaton is given by the regular expression.$ab^*b^*$$a^*b^*$$b^*b$$b^*ab^*$
2 votes
2 votes
1 answer
3
Arjun asked Dec 7, 2018
1,060 views
In the Given language $L=\{ab, aa, baaa\}$, ____ number of strings are in $L^*$baaabaaabaaaabaaabaaaabaabaaabaaa $1$$2$$3$$4$
3 votes
3 votes
1 answer
4