(a) Construct a minimal finite state machine that accepts the language, over…
PYQ GATE 2000
(a) Construct a minimal finite state machine that accepts the language, over {0,1}, of all strings that contain neither the substring 00 nor the substring 11.
(b) Consider the grammar
S → aSAb
S → ε
A → bA
A → εWhere S, A are non-terminal symbols with S being the start symbol; a,b are terminal symbols and ε is the empty string. This grammar generates strings of the form aⁱbʲ for some i, j ≥ 0, where i and j satisfy some condition. What is the condition on the values of i and j?
Sign up free to check your answer
Sign up freeLoading lesson…

