GATE 2012 CS (CS1) – Question 35

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple choice

L={ab,aa,baa}. Which strings belong to L*? 1: abaabaaabaa; 2: aaaabaaaa; 3: baaaaabaaaab; 4: baaaaabaa.

1,2,3
2,3,4
1,2,4
1,3,4

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 1,2,4

Explanation

Strings 1,2,4 admit tokenizations: ab·aa·baa·ab·aa; aa·aa·baa·aa; baa·aa·ab·aa respectively. String 3 has no valid factorization into ab,aa,baa (checking possible next tokens exhausts the prefixes). Hence 1,2,4, C. Each chosen token must belong to L.

More Regular Expressions and Finite Automata questions

GATE 2012 CS (CS1) Q56 – Over 0,1, every three-symbol substring must contain at most two zeros; all words shorter…
GATE 2013 CS (CS1) Q18 – L₁=∅ and L₂=a. Evaluate L 1L 2* L 1*.
GATE 2013 CS (CS1) Q43 – For the shown DFA A, which are false? 1: Its language complement is context-free. 2:…
GATE 2011 CS (CS1) Q52 – Over alphabet a, L=\ank:k>0\, with fixed positive integer n. Find the smallest DFA state…
GATE 2011 CS (CS1) Q55 – DFA D has transitions p:a→s,b→q; q:a→t,b→r; r loops on a,b; s,t are accepting and each…
GATE 2010 CS (CS1) Q49 – Which regular expression denotes all binary strings with an even number of ones?

All Regular Expressions and Finite Automata questions →