REST API Concepts

I'm trying to grasp the essence of REST API and i have some questions that i'd be happy if someone could clarify:

First
From Wikipedia:

it is a network of Web resources (a virtual state-machine) where the user progresses through the application by selecting resource identifiers such as http://www.example.com/articles/21 and resource operations such as GET or POST (application state transitions), resulting in the next resource's representation (the next application state) being transferred to the end user for their use.

What is the meaning of "application state"? As far as i understand, an application that exposes a REST API is stateless, so it doesn't have a "state" by definition? It just replies to client requests, which contain all the information needed by the server to respond to those requests. In other words, it doesn't hold any context. Am i correct?

Second
One of the 6 constraints is client-server architecture. Why is that a constraint? isn't it correct that every API is in a client-server architecture? eventually, API is Application Programming Interface. ??

Third

from here:

Using generic media types such as JSON is fundamentally not RESTful because REST requires the messages to be self-descriptive. Self-descriptiveness just means that the semantics of the data should travel with the data itself.

What is the original meaning behind the self-descriptiveness constraint, and does using a generic media-type violate this constraint?

Fourth
I've seen in many places that REST is not HTTP, and doesn't have to use HTTP as it's undelying protocol, it's just natural to use HTTP because the set of methods it has (GET, POST, PUT, DELETE). Can someone explain why is it natural for REST and give an example for another way to use REST other then HTTP?