Deterministic finite automaton: Difference between revisions

Revision as of 18:00, 12 June 2024

Revision as of 07:03, 6 July 2024

Line 2:

{{Use dmy dates|date=April 2020}}

{{Redirect-synonym|DFSA|[[drug-facilitated sexual assault]]}}

{{CS1 config|mode=cs1}}

[[File:DFA example multiplies of 3.svg|thumb|upright=1.1|An example of a deterministic finite automaton that accepts only binary numbers that are multiples of 3. The state S₀ is both the start state and an accept state. For example, the string "1001" leads to the state sequence S₀, S₁, S₂, S₁, S₀, and is hence accepted.]]

Line 96 ⟶ 97:

*[[Complementation of automata#With deterministic finite automata|Complement]]

*[[Kleene closure]]

*Reversal<ref name=rose/>

*Quotient{{citation<ref needed|datename=Januaryrose>{{cite 2015}}journal

| last = Rose | first = Gene F.

*Substitution{{citation needed|date=January 2015}}

| doi = 10.1016/S0022-0000(68)80029-7

*Homomorphism{{citation needed|date=January 2015}}

| issue = 2

| journal = [[Journal of Computer and System Sciences]]

| pages = 148–168

| title = Closures which Preserve Finiteness in Families of Languages

| volume = 2

| year = 1968}}</ref>

*Substitution<ref name=spanier>{{cite journal

| last = Spanier | first = E.

| doi = 10.1080/00029890.1969.12000214

| journal = American Mathematical Monthly

| jstor = 2316423

| mr = 241205

| pages = 335–342

| title = Grammars and languages

| volume = 76

| year = 1969}}</ref>

*Homomorphism<ref name=rose/><ref name=spanier/>

}}