Q1 – Let L = {ab, aa, baa}. Which of the following strings are not in L*.
abaabaaabaa
aaaabaaaa
baaaaabaaaab
baaaaabaa
(UGC NET DEC 2023)
Ans – (3)
Explanation – L* means that all the strings which are formed by concatenating ab, aa and baa.
Option 1 – ab| aa| baa| ab| aa. It belongs to L*.
Option 2 – aa| aa| baa| aa. It belongs to L*.
Option 3 – baa| aa| ab| aa| aa| b. It does not belong to L*.
Option 4 – baa| aa| ab| aa
So, option 3 is the right answer.
Q2 – Which of the following is not a palindromic subsequence of the string “ababcdabba”?
abcba
abba
abbbba
adba
(UGC NET DEC 2023)
Ans – (3, 4)
Explanation –
String | a | b | a | b | c | d | a | b | b | a |
Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Option 1 – abcba
String | a | b | c | b | a |
Index | 1 | 2 | 5 | 9 | 10 |
Option 2 – abba
String | a | b | b | a |
Index | 1 | 2 | 9 | 10 |
Option 3 – abbbba
String | a | b | b | b | b | a |
Index | 1 | 2 | 4 | 8 | 9 | 10 |
This is not correct.
Option 4 – adba
String | a | d | b | a |
Index | 1 | 6 | 9 | 10 |
This is not correct.
UGC NET corrects two options.
Q3 – Let A = {a, b} and L = A*. Let x = {an bn, n > 0}. The languages L ⋃ X and X are respectively :
Not regular, Regular
Regular, Regular
Regular, Not regular
Not Regular, Not Regular
(UGC NET DEC 2023)
Ans – (3)
Explanation – X is not regular (proven by the pumping lemma for regular languages). This is a well-known example of a non-regular language.
L = A* is regular because it contains all strings over the alphabet {a, b}.
The union of a regular language (L) and any language (X) can be expressed as – L ∪ X
Since L already contains everything in X, joining L U X does not add anything. As L is regular, this fact implies that its union with any subset stays regular.
Thus, we conclude that L ∪ X is regular.
Option 3 is the answer.
Q4 – The sum of minimum and maximum number of final states for a Deterministic Finite Automata (DFA) having ‘P’ state is equal to:
P
p-1
p + 1
p + 2
(UGC NET DEC 2023)
Ans – (3)
Explanation – A DFA must have the minimum final state is 1, because if there is no final state then there is no DFA.
The maximum final state in a ‘P’ state DFA is equal to ‘P’. Means all the states are final states.
On summing them, it is equal to P+1. Hence, option 3 is the answer.
Q5 – Which of the statement is/are CORRECT ?
(A) Moore and Mealy machines are finite state machines with output capabilities.
(B) Any given Moore machine has an equivalent Mealy machine.
(C) Any given Mealy machine has an equivalent Moore machine.
(D) Moore machine is not a finite state machine.
Choose the correct answer from the options given below :
(A) and (B) Only
(A), (B) and (C) Only
(B) and (D) Only
(A), (B) and (D) Only
(UGC NET DEC 2023)
Ans – (2)
Explanation – The Moore and Mealy machines are finite-state machines with outputs capability.
A Moore machine produces output based solely on its current state and the Mealy machine produces output depending on state and input symbols. generating output is their property. Thus, both machines are an FSM.
Also, every Moore machine has an equivalent Mealy machine, as in the case of mapping the transitions of inputs onto the state-dependent output. Also, every Mealy machine is actually able to be converted into an equivalent Moore machine. But it is wrong to state that a Moore machine is not an FSM, as Moore machines are a FSMs. The correct answer is option 2.
