Bissoy.com
Doctors Medicines MCQs Q&A

What is the complement of the language accepted by the NFA shown below? Assume ∑ = {a} and ϵ is the empty string

What is the complement of the language accepted by the NFA shown below? Assume ∑ = {a} and ϵ is the empty string Correct Answer {ϵ}

The correct answer is "option 2".

EXPLANATION:

NFA is:

[ alt="F1 Raju.S 05-05-21 Savita D1" src="//storage.googleapis.com/tb-img/production/21/05/F1_Raju.S_05-05-21_Savita_D1.png" style="width: 249px; height: 87px;">

Consider, ∑ = {a} and ϵ is the empty string

The ∑ = {a} and the NFA accept the following strings:

{a, aa, aaa, aaaa,……}

That means, the language accepted by the regular expression is {a+}

Therefore, the complement of the language is:

= {a* - a+}

= ϵ

Hence, the correct answer is "option 2".

Related Questions

Which of the following statement(s) is/are TRUE? (i) For every NFA with an arbitrary number of final states, there is an equivalent NFA with only one final state. (ii) A language that is accepted by a DFA will also be accepted by some NFA.
Suppliers(Sid: integer, sname:string, city:string, street:string) Parts(pid:integer, pname:string, color:string) Catalog(sid:integer, pid:integer, cost:real) Consider the following relational query on the above database: SELECT S.sname FROM Suppliers S  WHERE S.sid NOT IN (SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (SELECT P.pid FROM Parts P WHERE P.color < > ‘blue’)) Assume that relations corresponding to the above schema are not empty. Which of the following is the correct interpretation of the above query?
Consider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is ∑*. II. There exists a regular language A such that for all languages B, A ∩ B is regular. Which one of the following is CORRECT?
Statement 1: NFA computes the string along parallel paths. Statement 2: An input can be accepted at more than one place in an NFA. Which among the following options are most appropriate?
Consider the following problems. L(?) denotes the language generated by a grammar ?. L(?) denotes the language accepted by a machine ?. (I) For an unrestricted grammar ? and a string ?, whether ? ∈ (?) (II) Given a Turing machine M, whether L(M) is regular (III) Given two grammars ?1 and ?2, whether (?1) = (?2) (IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?
Read the passage carefully and choose thebest answer to each question out of the four alternativesand click the button corresponding to it. To know language is to be able to speak it; even a childwho does not yet attend school can speak his or herlanguage. In order to speak a language it is important tolisten to it and to read a few pages in it everyday. A childpicks up language and learns to talk just as (s)he learnsto walk. Walking and talking comes naturally to a child asit grows. In our country, a child may grow up speakingmore than one language, if these languages are spoken inthe home and in the neighbourhood. we call this multilingualism. A child speaks a language or languagesmuch before (s)he starts going to school. To know alanguage then is first of all to be able to speak it as easilyand naturally as a tree year old child does. Later on thechild will learn to read and write in that language. In orderto read and write in a language, one has to speak it. But itis possible to speak a language but not able to read orwrite in it. A baby does not speak until it is nine monthsold but it understands a few words at six months of age.It has been listening ever since it was born, and even alittle before that. So the first strategy in speaking alanguage is to listen. It is necessary for one to __________ the language before(s)he writes in that language.
How many objects will be created? String a = new String("Examveda"); String b = new String("Examveda"); String c = "Examveda"; String d = "Examveda";
Choose the correct option for the following two statements: A: 1’s complement circuit is more complex than that of 2’s complement method. B: The extra carry is considered in 1’s complement whereas it is disregarded in 2’s complement method.
Read the passage carefully and choose thebest answer to each question out of the four alternativesand click the button corresponding to it. To know language is to be able to speak it; even a childwho does not yet attend school can speak his or herlanguage. In order to speak a language it is important tolisten to it and to read a few pages in it everyday. A childpicks up language and learns to talk just as (s)he learnsto walk. Walking and talking comes naturally to a child asit grows. In our country, a child may grow up speakingmore than one language, if these languages are spoken inthe home and in the neighbourhood. we call thismultilingualism. A child speaks a language or languagesmuch before (s)he starts going to school. To know alanguage then is first of all to be able to speak it as easilyand naturally as a tree year old child does. Later on thechild will learn to read and write in that language. In orderto read and write in a language, one has to speak it. But itis possible to speak a language but not able to read orwrite in it. A baby does not speak until it is nine monthsold but it understands a few words at six months of age.It has been listening ever since it was born, and even alittle before that. So the first strategy in speaking alanguage is to listen. To know a language one must be able to?
Pipes A and B are used to fill the tank. A can fill the tank twice as fast as B. Pipe C and D can empty the tank. D takes same time to empty the tank as taken by B to fill it. Pipe C can empty tank in 6 hours. If all 4 are opened together, how much hour would it take to fill the tank? (Assume: D can empty tank twice as fast as C.)