Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Automata Eliminating null Transitions

Automata Eliminating null Transitions with automata tutorial, finite automata, dfa, nfa, regexp, transition diagram in automata, transition table, theory of automata, examples of dfa, minimization of dfa, non deterministic finite automata, etc.

<< Back to AUTOMATA

Eliminating ε Transitions

NFA with ε can be converted to NFA without ε, and this NFA without ε can be converted to DFA. To do this, we will use a method, which can remove all the ε transition from given NFA. The method will be:

  1. Find out all the ε transitions from each state from Q. That will be called as ε-closure{q1} where qi ∈ Q.
  2. Then δ' transitions can be obtained. The δ' transitions mean a ε-closure on δ moves.
  3. Repeat Step-2 for each input symbol and each state of given NFA.
  4. Using the resultant states, the transition table for equivalent NFA without ε can be built.


Convert the following NFA with ε to NFA without ε.

Eliminating Null Transitions

Solutions: We will first obtain ε-closures of q0, q1 and q2 as follows:

ε-closure(q0) = {q0}
ε-closure(q1) = {q1, q2}
ε-closure(q2) = {q2}

Now the δ' transition on each input symbol is obtained as:

δ'(q0, a) = ε-closure(δ(δ^(q0, ε),a))
              = ε-closure(δ(ε-closure(q0),a))
              = ε-closure(δ(q0, a))
              = ε-closure(q1)
              = {q1, q2}

δ'(q0, b) = ε-closure(δ(δ^(q0, ε),b))
              = ε-closure(δ(ε-closure(q0),b))
              = ε-closure(δ(q0, b))
              = Ф

Now the δ' transition on q1 is obtained as:

δ'(q1, a) = ε-closure(δ(δ^(q1, ε),a))
              = ε-closure(δ(ε-closure(q1),a))
              = ε-closure(δ(q1, q2), a)
              = ε-closure(δ(q1, a) ∪ δ(q2, a))
              = ε-closure(Ф ∪ Ф)
              = Ф

δ'(q1, b) = ε-closure(δ(δ^(q1, ε),b))
              = ε-closure(δ(ε-closure(q1),b))
              = ε-closure(δ(q1, q2), b)
              = ε-closure(δ(q1, b) ∪ δ(q2, b))
              = ε-closure(Ф ∪ q2)
              = {q2}

The δ' transition on q2 is obtained as:

δ'(q2, a) = ε-closure(δ(δ^(q2, ε),a))
              = ε-closure(δ(ε-closure(q2),a))
              = ε-closure(δ(q2, a))
              = ε-closure(Ф)
              = Ф

δ'(q2, b) = ε-closure(δ(δ^(q2, ε),b))
              = ε-closure(δ(ε-closure(q2),b))
              = ε-closure(δ(q2, b))
              = ε-closure(q2)
              = {q2}

Now we will summarize all the computed δ' transitions:

δ'(q0, a) = {q0, q1}
δ'(q0, b) = Ф
δ'(q1, a) = Ф
δ'(q1, b) = {q2}
δ'(q2, a) = Ф
δ'(q2, b) = {q2}

The transition table can be:

States a b
→q0 {q1, q2} Ф
*q1 Ф {q2}
*q2 Ф {q2}

State q1 and q2 become the final state as ε-closure of q1 and q2 contain the final state q2. The NFA can be shown by the following transition diagram:

Eliminating Null Transitions

Related Links:

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf