Working on: Richard Johnsonbaugh. (2018). Discrete Mathematics, 8/e (p. 607) 2. Determine whether the given grammar is context-sensitive, context-free, regular, or none of these. Provide all classifications that apply. $T = \{a, b\}, N = \{\sigma, A, B\}$, with productions: \begin{aligned} ...

The problem is the following. On input, an undirected graph $G = (V, E)$. Question: can $V$ be partitioned into two (disjoint) subsets $V = V_1 \cup V_2$, with $-1 \leq |V_1| - |V_2| \leq 1$ so that the graph $(V_1, V_2, E)$ is bipartite? Alternative formulation #1: can a graph be partitioned int...