Regulatory agencies in the U.S., e.g., Occupational Safety and Health Administration (OSHA), Nuclear Regulatory Commission (NRC), Environmental Protection Agency (EPA) develop regulations to implement laws. When parties subject to these regulations violate them, they are said to be out of compliance or non-compliant. In such cases, the regulator may issue Notices of Violation, which could carry civil penalties, depending on factors such as severity, adverse impact, willfulness, and repetitive nature of the violation. So with regard to your first example, the correct word is non-compliant:
Illegal is to law as non-compliant is to regulation.
You second example is different, because the Army is not a regulator in the sense that OSHA, NRC, and EPA are. That is not to say, however, that the Army can't make rules or establish requirements applicable to those in the Army; so one soldier could say to a subordinate, "That's against [Army] regulations". So, as to your second example, one could write:
"It is against (Army) regulations for servicemen enlisted in the US
Army to have mohawks."
Or one soldier could say to another soldier sporting a mohawk:
"That's a non-regulation haircut."
Several commenters have mentioned non-regulation.