Question

The set {0,1,#}+-{b1#b2#…#bn|n>=1} where bi is the binary representation of i is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive

Answer 1

Answer on Question#38641 – Math - Other

We have the set $S = \{0,1,\#\} + - \{b1\# b2\# \ldots\# bn|n \geq 1\}$

The set describes all strings of $0's$ and $1's$ separated by $\#$, where there's at least one pair of consecutive $0's$ and $1's$ having equal length. For example 00#00, 0#00#000#00, and 000#00#0#000 are in $S$, while #00#000, 00, and #00 are not in $S$. We can see that the context-free grammar generates the set, so the set is context-free.

Answer: B.