Sachverhalt:
A.
Die Staatsanwaltschaft Basel-Stadt erklärte A._ am 19. Mai 2016 mittels Strafbefehl der Fälschung von Ausweisen sowie der rechtswidrigen Einreise schuldig und bestrafte sie mit einer unbedingten Freiheitsstrafe von 45 Tagen.
A._ erhob am 3. Juni 2019 Einsprache gegen den Strafbefehl und stellte gleichzeitig, als Eventualantrag, ein Revisionsgesuch. Am 6. Juni 2019 überwies die Staatsanwaltschaft den Strafbefehl an das Strafgericht Basel-Stadt.
B.
Das Strafgericht stellte am 7. Juni 2019 fest, dass die Einsprache gültig erhoben wurde und wies die Akten an die Staatsanwaltschaft zwecks neuer Eröffnung des Strafbefehls zurück. Dagegen erhob die Staatsanwaltschaft Beschwerde.
C.
In Gutheissung der Beschwerde hob das Appellationsgericht Basel-Stadt am 30. September 2019 die Verfügung des Strafgerichts auf und stellte fest, dass der Strafbefehl vom 19. Mai 2016 in Rechtskraft erwachsen ist.
D.
A._ führt Beschwerde in Strafsachen. Sie beantragt, der Entscheid des Appellationsgerichts sei aufzuheben und es sei festzustellen, dass die Einsprache gegen den Strafbefehl gültig erhoben worden sei. Die Angelegenheit sei folglich an das Strafgericht zur Durchführung des Hauptverfahrens zurückzuweisen. Für das Verfahren vor dem Bundesgericht sei ihr die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
Das Appellationsgericht und die Staatsanwaltschaft beantragen, die Beschwerde sei abzuweisen. A._ replizierte.

Erwägungen:
1.
1.1. Die Beschwerdeführerin rügt, sie spreche nur Französisch und der in deutscher Sprache verfasste Strafbefehl sei in Missachtung von <ref-law> nicht übersetzt worden. Das von der Vorinstanz erwähnte Dokument "Information für fremdsprachige Personen" befinde sich nicht in den Akten und genüge dem gesetzlichen Anspruch auf Übersetzung der wichtigsten Verfahrenshandlungen ohnehin nicht.
1.2. Die Vorinstanz erwägt, ein Anspruch auf vollständige Übersetzung sämtlicher Verfahrenshandlungen bestehe nach <ref-law> nicht. Nach ständiger Rechtsprechung des Appellationsgerichts genüge es, wenn dem in deutscher Sprache abgefassten Strafbefehl das Formular "Information für fremdsprachige Personen" beigelegt sei. Es handle sich hierbei um ein in acht Sprachen (Albanisch, Englisch, Französisch, Italienisch, Rumänisch, Serbisch, Spanisch, Türkisch) abgefasstes Merkblatt, in welchem das Vorgehen zusammengefasst werde, sollte der Empfänger den Strafbefehl anfechten wollen. Es werde insbesondere ausdrücklich erwähnt, dass eine Einsprache innert zehn Tagen erfolgen müsse. Darüber hinaus werde unter Angabe der Homepage der Staatsanwaltschaft, deren Adresse, Öffnungszeiten und Telefonnummer auf eine Übersetzungshilfe hingewiesen.
1.3.
1.3.1. Nach <ref-law> wird der beschuldigten Person, auch wenn sie verteidigt wird, in einer ihr verständlichen Sprache mindestens der wesentliche Inhalt der wichtigsten Verfahrenshandlungen mündlich oder schriftlich zur Kenntnis gebracht. Ein Anspruch auf vollständige Übersetzung aller Verfahrenshandlungen sowie der Akten besteht nicht. Bei Strafbefehlen sind nach der Rechtsprechung zumindest das Dispositiv und die Rechtsmittelbelehrung zu übersetzen (<ref-ruling> E. 1.3.3; Urteile 6B_667/2017 vom 15. Dezember 2017 E. 5.4; 6B_277/2019 vom 5. Juli 2019 E. 2.2.2).
Das von der Vorinstanz erwähnte Merkblatt "Information für fremdsprachige Personen" befindet sich - wie die Beschwerdeführerin zutreffend rügt - nicht in den Akten. Die Staatsanwaltschaft reichte dieses erstmals zusammen mit ihrer Vernehmlassung ein, was unzulässig ist (<ref-law>). Den Erwägungen der Vorinstanz ist dennoch zu entnehmen, dass das Merkblatt lediglich Informationen allgemeiner Natur zum Strafbefehlsverfahren und Hinweise auf eine "Übersetzungshilfe" enthält. Die Beilage eines solchen Informationsblatts einem in deutscher Sprache verfassten Strafbefehl genügt - entgegen der Praxis der Vorinstanz - den Anforderungen von <ref-law> nicht, zumal damit keine Übersetzung des im konkreten Fall gefällten Dispositivs erfolgt. Dass die Beschwerdeführerin nur Französisch spricht, stellt die Vorinstanz nicht in Abrede.
1.3.2. Aus einer unrichtigen Rechtsmittelbelehrung dürfen den Parteien keine Nachteile erwachsen. Eine Partei ist freilich nur dann geschützt, wenn sie sich nach Treu und Glauben (<ref-law>, <ref-law>) auf die fehlerhafte Rechtsmittelbelehrung verlassen durfte. Wer die Unrichtigkeit erkannte oder bei gebührender Aufmerksamkeit hätte erkennen können, kann sich nicht auf den Vertrauensschutz berufen. Nur eine grobe prozessuale Unsorgfalt der betroffenen Partei oder ihres Anwalts vermag eine unrichtige Rechtsmittelbelehrung aufzuwiegen. Wann eine grobe prozessuale Unsorgfalt vorliegt, beurteilt sich nach den konkreten Umständen und den Rechtskenntnissen der betreffenden Person (<ref-ruling> E. 8.3.2; Urteil 6B_667/2017 vom 15. Dezember 2017 E. 5.2). Diese Rechtsprechung kommt auch dann zur Anwendung, wenn die Rechtsmittelbelehrung im Missachtung von <ref-law> nicht übersetzt wurde (Urteil 6B_667/2017 vom 15. Dezember 2017 E. 5.4). Umso mehr muss dies der Fall sein, wenn eine Übersetzung des Dispositivs fehlt, denn nur diese erlaubt es der beschuldigten Person, die Tragweite der mit dem Strafbefehl ausgesprochenen Sanktion und die Notwendigkeit einer Einsprache einzuschätzen.
Die Beschwerdeführerin wurde am 18. Mai 2016 um 19:10 Uhr durch die Grenzwache am Grenzübergang U._ kontrolliert. In diesem Rahmen soll sie einen verfälschten kamerunischen Reisepass vorgewiesen haben. Gleichentags verfügte das kantonale Migrationsamt die vorläufige Festnahme. Am darauffolgenden Tag, den 19. Mai 2016, erliess die Staatsanwaltschaft den zur Diskussion stehenden Strafbefehl, welcher noch am selben Tag, um 17:00 Uhr, durch die Polizei der Beschwerdeführerin ausgehändigt wurde. Anschliessend wurde die Beschwerdeführerin aus der Haft entlassen. Eine Einvernahme durch die Staatsanwaltschaft fand nicht statt.
Die Beschwerdeführerin musste zwar infolge des Vorwurfs, mit einem gefälschten Dokument eingereist zu sein, mit strafrechtlichen Massnahmen rechnen. Aufgrund der Tatsache, dass die Staatsanwaltschaft sie nicht einvernahm und sie nach einem Tag aus der Haft entlassen wurde, musste sie aber nicht damit rechnen, mittels eines Strafbefehls mit einer unbedigten Freiheitsstrafe bestraft worden zu sein. Ihr kann damit keine grobe prozessuale Unsorgfalt vorgeworfen werden, welche es ihr verwehren würde, sich auf die fehlende Übersetzung zu berufen. Der blosse Zeitablauf begründet - entgegen der Ansicht der Vorinstanz (Entscheid, S. 6) - keinen Rechtsmissbrauch. Nicht zu beurteilen ist vorliegend die Frage der Nichtigkeit des Strafbefehls, womit sich der von der Staatsanwalt im Rahmen ihrer Vernehmlassung erwähnte <ref-ruling> als nicht einschlägig erweist.
2.
Die Beschwerde ist gutzuheissen. Der angefochtene Entscheid ist aufzuheben und die Sache an das erstinstanzliche Gericht zur Durchführung des Hauptverfahrens zurückzuweisen (<ref-law>).
Für das bundesgerichtliche Verfahren sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Die Beschwerdeführerin hat Anspruch auf eine angemessene Parteientschädigung (<ref-law>). Diese ist praxisgemäss dem Rechtsvertreter auszurichten. Das Gesuch der Beschwerdeführerin um unentgeltliche Rechtspflege und Verbeiständung wird gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 30. September 2019 wird aufgehoben und die Sache wird an das Strafgericht Basel-Stadt zur Durchführung des Hauptverfahrens zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Basel-Stadt hat dem Vertreter der Beschwerdeführerin, Advokat Andreas Noll, eine Parteientschädigung von Fr. 3'000.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien, dem Appellationsgericht des Kantons Basel-Stadt, Einzelgericht, und dem Strafgericht Basel-Stadt schriftlich mitgeteilt.
Lausanne, 8. Mai 2020
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Moses