Decidability in Automata: Can Finite Automata and Regular Expressions Accept Any String? 🤖

In this lecture concept of decidability in automata has been discussed in detail. What id decidability and decidable problems has also been discussed. Decidability is making decision about following:
Is given FA/RE accept any string or not?
Is given FA/RE represents finite or infinite language?
Whether two languages are equivalent or not?
The problems that solve in finite steps and their answer is Yes or No, such problems are called decidable problems.

Is FA/RE Accept any String or Not? we discussed it with help of solved example.

To find out that given FA/RE accept any string or not
We will perform following steps on given FA, If we have given RE then first we construct FA from RE then we perform following steps.
Mark the initial state.
Mark the states that are connected with initial states.
Remove the edges that connect initial state with other states.
Remove the edges of next marked state and if next marked state edges connected with another state then also marked that state.
Repeat the above process until final state is marked
If we are unable to reach to final state, it means our FA does not accept any string
If we reach to final state, it means our FA accept any string
what is decidability?
what is decidability in automata?
decidbility in urdu
decidability with examples
decidability in hindi
#AzComputing
#Decidability
#Automata