String questions look like simple counting until one word changes the universe: non-empty, proper, substring, subsequence or lexicographic. Apply one memorised formula without checking that word, and you can land exactly on a distractor. This set solves 12 published MCQs through concrete strings, interval counts, prefix checks, concatenation traces and a finite-memory counterexample. KnowledgeGate has 20+ published questions covering Basics & String Ops under Theory of Computation, within CS Fundamentals. Each question below also links to its solved practice page, so you can attempt it before reading the explanation. The goal is careful interpretation before calculation.
1. Fix the vocabulary before solving: one string, six different objects
Let w = GATE, with |w| = 4. Its alphabet is {G, A, T, E}; the empty string is ε, with |ε| = 0. Also, GA · TE = GATE and wᴿ = ETAG.
Its prefixes are ε, G, GA, GAT, GATE; its suffixes are ε, E, TE, ATE, GATE. Under Question 1's convention, the non-empty proper prefixes are G, GA, GAT, so there are 4 - 1 = 3. Some texts call ε proper because only the full string is excluded. Check the convention.
AT is both a substring and a subsequence of GATE. GE is a subsequence but not a substring. TG is neither. For indexed substrings of w[1..4], choose (i,j) with 1 ≤ i ≤ j ≤ 4. That gives 4 + 3 + 2 + 1 = 10 non-empty occurrences, or 11 after adding ε.
For a fuller concept pass, use the Theory of Computation (TOC): Worked Examples Guide.
2. Prefix and substring counts: decide whether length zero is included
Question 1
In a string of length n, how many proper prefixes can be generated?
(a) 2ⁿ
(b) n
(c) n(n + 1)/2
(d) n − 1
Answer: (d), n − 1, under the non-empty convention. For w = abcde, n = 5, and the allowed prefixes are a, ab, abc, abcd, giving 4 = 5 - 1. This excludes ε and the full string. If only w is excluded, ε remains and the count becomes n; check the convention. Solved practice
Question 2
If you have a string of length 5, then how many non-empty substrings will it have?
(a) 10
(b) 15
(c) 30
(d) 5
Answer: (b), 15. The five possible lengths contribute 5, 4, 3, 2, 1 substrings, so 5 + 4 + 3 + 2 + 1 = 15. These are occurrences by position; repeated symbols can produce fewer distinct values. Solved practice
Question 3
The number of substrings (of all lengths inclusive) that can be formed from a character string of length n is
(a) n!
(b) n²
(c) n(n − 1)/2 − 1
(d) n(n + 1)/2 + 1
Answer: (d), n(n + 1)/2 + 1. Non-empty lengths contribute n + (n - 1) + ... + 1 = n(n + 1)/2; add the one empty string. For w = abc, the six non-empty occurrences are a, b, c, ab, bc, abc. With ε, 7 = 3 × 4/2 + 1. Solved practice
Question 4
The number of substrings that can be formed from string given by
\(a \: d \: e \: f \: b \: g \: h \: n \: m \: p\)
is
(a) 10
(b) 45
(c) 55
(d) 56
Answer: (d), 56, with the empty substring included. The ten symbols give 10 × 11/2 = 55 non-empty occurrences. Add ε to obtain 56. If only non-empty substrings are requested, the answer is 55; this item includes length zero. Solved practice
3. Lexicographic order and nested string operations: trace left to right
Question 5
Find the lexicographic ordering of the bit strings given below based on the ordering 0<1.
(A) 001
(B) 010
(C) 011
(D) 0001
(E) 0101
Choose the correct answer from the options given below:
(a) 001 < 010 < 011 < 0001 < 0101
(b) 0001 < 001 < 010 < 0101 < 011
(c) 0001 < 0101 < 001 < 010 < 011
(d) 001 < 010 < 0001 < 0101 < 011
Answer: (b). First differences give 0001 < 001 and 001 < 010. A prefix precedes its longer extension, so 010 < 0101. Position 3 gives 0101 < 011 because 0 < 1. The order is 0001 < 001 < 010 < 0101 < 011; sorting by length would fail. Solved practice
Question 6
A language with string manipulation facilities uses the following operations. head(s)- returns the first character of the string s tail(s)- returns all but the first character of the string s concat(sl, s2)- concatenates string s1 with s2. The output of concat(head(s), head(tail(tail(s)))), where s is acbc is
(a) ab
(b) ba
(c) ac
(d) as
Answer: (a), ab. Preserve the nesting and evaluate inside out:
Step | Value |
|---|---|
|
|
|
|
|
|
|
|
Separately, head(s) = a, so concat(a,b) = ab. The stem's sl evidently means the first argument. Solved practice
Question 7
Let u = ‘1101’, v = ‘0001’, then uv = 11010001 and vu = 00011101. Using the given information what is the identity element for the string?
(a) u-1
(b) v-1
(c) uv-1
(d) ε
Answer: (d), ε. A two-sided identity e satisfies ue = u and eu = u for every string. Here, 1101ε = 1101 and ε1101 = 1101; likewise for 0001. Non-empty strings have no concatenation inverse because concatenation adds length rather than cancelling symbols. Solved practice
4. Counting constrained bit strings: inclusion-exclusion with actual set sizes
Question 8
The number of bit strings of length 8 that will either start with 1 or end with 00 is?
(a) 32
(b) 128
(c) 160
(d) 192
Answer: (c), 160. For strings starting with 1, seven bits remain free, so |A| = 2⁷ = 128. Ending with 00 leaves six free: |B| = 2⁶ = 64. Their overlap leaves five free: |A ∩ B| = 2⁵ = 32. Thus |A ∪ B| = 128 + 64 - 32 = 160. Option (d), 192, double-counts the overlap. Solved practice
Next, try the broader Theory of Computation MCQs.
5. Prefix, suffix, substring and subsequence: test contiguity explicitly
Question 9
Consider the string “GATECSELECTURE”
S1: “GATECSELECTURE” is a prefix of given string.
S2: “GATECSELECTURE” is a suffix of given string.
S3: “CSELECTURE” is a subsequence of given string.
S4: “GTCS” is a substring of given string.
Which of the above statement is/are FALSE?
(a) Only S1 and S2
(b) Only S4
(c) Only S3 and S4
(d) Only S3
Answer: (b), Only S4. The positions are 1:G, 2:A, 3:T, 4:E, 5:C, 6:S, 7:E, 8:L, 9:E, 10:C, 11:T, 12:U, 13:R, 14:E. S1 and S2 are true because a string is its own prefix and suffix. Positions 5 to 14 spell CSELECTURE, so S3 is true. G,T,C,S occur at 1,3,5,6, not contiguously. GTCS is a subsequence, not a substring, so only S4 is false. Solved practice
6. What finite-state memory can and cannot do
Question 10
A fixed deterministic finite-state machine (FSM), with no unbounded buffer, reads one pair of input digits per step from left to right and must output the corresponding sum digits in the same pass without revising earlier output. The two integers may have arbitrary length, and the inputs and sum use the standard most-significant-digit-first order. The statement that such an FSM can always add the two integers is:
(a) True
(b) False
(c) may be true
(d) none of the above
Answer: (b), False. Compare 1200 + 2300 = 3500 and 1299 + 2301 = 3600. The first two input pairs match, (1,2) then (2,3), but the second output digit is 5 versus 6 because an unseen suffix creates a carry. The suffix may be arbitrarily distant. A fixed-state machine cannot buffer an unbounded prefix or revise output. With least-significant-digit-first input, only carry 0 and carry 1 are needed. Solved practice
Question 11
Consider the statements below:
S1: A Finite automata has no memory at all.
S2: A Finite automata has a limited memory.
S3: For all Moore machines we have an equivalent Finite automaton.
Which of the following statements is/are TRUE
(a) Only S2
(b) Only S1 and S3
(c) Only S1 and S2
(d) Only S2 and S3
Answer: (d), Only S2 and S3. The current state is finite memory. With k states, a machine distinguishes only k stored situations, so S1 is false and S2 true. For S3, ignore a Moore machine's output labels and retain its finite states and input transitions. This does not make a transducer and a language recogniser behaviourally identical. Solved practice
Next, try Finite Automata MCQs: 10 Solved DFA and NFA (GATE).
7. Language universe, complement and the final checking routine
Question 12
The complement of a language will only be defined when and only when the ______ over the language is defined.
(a) Alphabet
(b) Word
(c) String
(d) Grammar
Answer: (a), Alphabet. If L ⊆ Σ*, then L̅ = Σ* \ L. For L = {0} over Σ = {0,1}, the complement includes ε, 1, 00, 01, 10, 11, .... Over Γ = {0}, it includes ε, 00, 000, ..., but not 1. The alphabet changes the universe and therefore the complement; a grammar does not set that universe. Solved practice
The short checking routine
Write the universe, usually Σ*, and mark whether ε is included. Then ask whether order matters and whether selected symbols must be contiguous. Test the rule on one small string before choosing an option. Remember the three traps here: n(n + 1)/2 becomes +1 only when ε is counted; GTCS is a subsequence but not a substring of GATECSELECTURE; and inclusion-exclusion gives 128 + 64 - 32 = 160, not 192. For structured concept revision, continue with the Theory Of Computation / Automata Theory course.
