No DFA for the regular language 0*1*.

ajiten · 11-03-2023, 05:14 AM

Find the DFA for the regular language 0*1*

Even in JFLAP, there is no option seemingly to convert NFA for the above regular language to DFA,
as ε transitions are not allowed in DFA.

So, can conclude that there are no DFA for this particular type of regular language(s).

NevemTeve · 11-03-2023, 07:37 AM

Code:

State Type       Transition on '0' Transition on '1'
A     Start,Stop A                 B
B     Stop       Error             B

ntubski · 11-03-2023, 07:41 AM

Quote:

no option seemingly to convert NFA for the above regular language to DFA,
as ε transitions are not allowed in DFA.

https://www.geeksforgeeks.org/conver...on-nfa-to-nfa/

ajiten · 11-03-2023, 09:30 PM

Quote:

Originally Posted by NevemTeve

Code:

State Type       Transition on '0' Transition on '1'
A     Start,Stop A                 B
B     Stop       Error             B

Your transition table seems for 0*1+, as don't need ε-transition to move from the state A to the state B.

ajiten · 11-03-2023, 09:36 PM

Quote:

Originally Posted by ntubski

https://www.geeksforgeeks.org/conver...on-nfa-to-nfa/

Where is given in the stated link, that ε-transition can be represented by a transition, on a symbol in the alphabet (Σ)?
Please note that the stated regular language is not: 0* + 1*; in which case it was quite easy to build DFA, with 1 state as both the initial & the final state.

NevemTeve · 11-04-2023, 12:04 AM

> Your transition table seems for 0*1+

That would be the case is 'A' weren't a stop-state. Please check every state again, and verify which ones are stop-states.

Note: it might help if we rewrite the expression as (ε|0+)(ε|1+) =
ε | 0+ | 1+ | 0+1+

ajiten · 11-04-2023, 02:39 AM

Quote:

Originally Posted by NevemTeve

> Your transition table seems for 0*1+

That would be the case is 'A' weren't a stop-state. Please check every state again, and verify which ones are stop-states.

Note: it might help if we rewrite the expression as (ε|0+)(ε|1+) =
ε | 0+ | 1+ | 0+1+

Thanks for that, but seems this simple example is dealt nowhere, in literature, or online.
Also, based on your example; can take the regular expression for the regular language: 0* + 1*; as: ε | 0+ | 1+ | (0 U 1)+

NevemTeve · 11-04-2023, 04:52 AM

I don't get your point, 0* | 1* can be rewritten as ε | 0+ | 1+

Note: here '+' means 'one or more occurances', '|' means alternatives
If you don't like this notattion, then write it this way:

0*+1* = ε+00*+11*

I.e. let's not use plus sign for two different things in the same expression.

ntubski · 11-04-2023, 08:05 AM

Quote:

Originally Posted by ajiten

Where is given in the stated link, that ε-transition can be represented by a transition, on a symbol in the alphabet (Σ)?

A single ε-transition can't necessarily be represented by a single transition on an alphabet symbol. The link shows how to convert a whole ε-NFA to an equivalent NFA with no ε-transitions. Hence the title "Conversion of Epsilon-NFA to NFA".

ajiten · 11-04-2023, 02:23 PM

Quote:

Originally Posted by ntubski

A single ε-transition can't necessarily be represented by a single transition on an alphabet symbol. The link shows how to convert a whole ε-NFA to an equivalent NFA with no ε-transitions. Hence the title "Conversion of Epsilon-NFA to NFA".

Sorry, that was there in the link.

Request more details on your opening sentence, as to when it is not possible (it is possible in the given regular language):
'A single ε-transition can't necessarily be represented by a single transition on an alphabet symbol.'

ntubski · 11-05-2023, 12:21 AM

Quote:

Originally Posted by ajiten

Sorry, that was there in the link.

Request more details on your opening sentence, as to when it is not possible (it is possible in the given regular language):
'A single ε-transition can't necessarily be represented by a single transition on an alphabet symbol.'

If you follow the algorithm in the link, and an ε-transition gets turned into multiple alphabet transitions, then it can't be represented by a single one.