Is Language of All Binary-Digit Strings Not Containing Substring 0100 or Suffix 010 Context-Free?

Question

Let $\Sigma$ be the alphabet consisting of the symbols {0,1}, let $\Sigma^{*}$ be its Kleene closure, and let $R$ be defined by

$R = \{w \in \Sigma^{*} \mid (0100 \text{ is not a substring of }w) \wedge (010 \text{ is not a suffix of }w)\}$.

Is $R$ a context-free language, and if so, what would be a grammar or FSM describing it?

Thank you...

Answer 1

$R$ is not just context-free: it’s regular. Here is a the transition table for a DFA that recognizes $R$; $q_0$ is the initial state, and $q_0,q_1$, and $q_2$ are the acceptor states.

$$\begin{array}{c|c|c} q&a&\delta(q,a)\\\hline q_0&0&q_1\\ q_0&1&q_0\\ q_1&0&q_1\\ q_1&1&q_2\\ q_2&0&q_3\\ q_2&1&q_0\\ q_3&0&q_4\\ q_3&1&q_2\\ q_4&0&q_4\\ q_4&1&q_4 \end{array}$$

Draw the automaton and check that it is at $q_3$ if and only if the current input ends in $010$, and it reaches $q_4$ if and only if the input has a substring $0100$.