Exams › GATE › Technical

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0,1}, and has the set of states {s,p,q,r}, with s being the start state and p being the only final state. Which one of the following regular expressions correctly describes the language accepted by A?

1. 1(0*11)*
2. 0(0 + 1)*
3. 1(0 + 11)*
4. 1(110*)*

Correct answer: 1(0 + 11)*

Solution

The correct option, 1(0 + 11)*, accurately represents the language accepted by the DFA because it starts with a '1' followed by any combination of '0's and '11's, which aligns with the transitions and final state conditions of the automaton.

Related GATE Technical questions

• Which one of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
• Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?
• Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?
• Suppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.
• An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let k be the number of keys, m be the number of slots in the hash table, and k > m. Which one of the following is the best hashing strategy to counteract the adversary?
• The output of a 2-input multiplexer is connected back to one of its inputs as shown in the figure. Match the functional equivalence of this circuit to one of the following options.

⚔️ Practice GATE Technical free + battle 1v1 →