1 vote

Proving that a language whose strings have prime length is not context-free

Clearly $1^p$ belongs to $L$ for any prime $p$. If $L$ were regular, then, by the pumping lemma, for large enough prime $p$, you can write $1^p$ as $xyz$, where $y$ is non-empty and any string of the ...
Rob Arthan's user avatar
  • 45.9k
1 vote

Formalizing Real World Sentence In Intuitionistic Logic?

The two statements are also equivalent in intuitionist logic. For suppose (1) holds. Now suppose $W \implies P$. Then $W \implies (P \lor M \lor I \lor D)$; contradiction. Thus, we must have $\neg (W \...
Mark Saving's user avatar
  • 31.3k

Only top scored, non community-wiki answers of a minimum length are eligible