Question

the non acceptance of language by FA is​

Answer 1

Explanation:

Subjects to be Learned

Language accepted by DFA

Contents

Here we are going to formally define what is meant by a DFA (deterministic finite automaton) accepting a string or a language.

A string w is accepted by a DFA < Q , , q0 , , A > , if and only if *( q0 , w ) A . That is a string is accepted by a DFA if and only if the DFA starting at the initial state ends in an accepting state after reading the string.

A language L is accepted by a DFA < Q , , q0 , , A > , if and only if L = { w | *( q0 , w ) A } . That is, the language accepted by a DFA is the set of strings accepted by the DFA.

Example 1 :

This DFA accepts {} because it can go from the initial state to the accepting state (also the initial state) without reading any symbol of the alphabet i.e. by reading an empty string . It accepts nothing else because any non-empty symbol would take it to state 1, which is not an accepting state, and it stays there.

Example 2 :

This DFA does not accept any string because it has no accepting state. Thus the language it accepts is the empty set .

Example 3 : DFA with one cycle

This DFA has a cycle: 1 - 2 - 1 and it can go through this cycle any number of times by reading substring ab repeatedly.

To find the language it accepts, first from the initial state go to state 1 by reading one a. Then from state 1 go through the cycle 1 - 2 - 1 any number of times by reading substring ab any number of times to come back to state 1. This is represented by (ab)*. Then from state 1 go to state 2 and then to state 3 by reading aa. Thus a string that is accepted by this DFA can be represented by a(ab)*aa .

Example 4 : DFA with two independent cycles

This DFA has two independent cycles: 0 - 1 - 0 and 0 - 2 - 0 and it can move through these cycles any number of times in any order to reach the accepting state from the initial state such as 0 - 1 - 0 - 2 - 0 - 2 - 0. Thus a string that is accepted by this DFA can be represented by ( ab + bb )*.

Example 5 : DFA with two interleaved cycles

This DFA has two cycles: 1 - 2 - 0 - 1 and 1 - 2 - 3 - 1.

To find the language accepted by this DFA, first from state 0 go to state 1 by reading a ( any other state which is common to these cycles such as state 2 can also be used instead of state 1 ). Then from state 1 go through the two cycles 1 - 2 - 0 - 1 and 1 - 2 - 3 - 1 any number of times in any order by reading substrings baa and bba, respectively. At this point a substring a( baa + bba )* will have been read. Then go from state 1 to state 2 and then to state 3 by reading bb. Thus altogether a( baa + bba )*bb will have been read when state 3 is reached from state 0.

Example 6 :

This DFA has two accepting states: 0 and 1. Thus the language that is accepted by this DFA is the union of the language accepted at state 0 and the one accepted at state 1. The language accepted at state 0 is b* . To find the language accepted at state 1, first at state 0 read any number of b's. Then go to state 1 by reading one a. At this point (b*a) will have been read. At state 1 go through the cycle 1 - 2 - 1 any number of times by reading substring ba repeatedly. Thus the language accepted at state 1 is b*a(ba)* .

There is a systematic way of finding the language accepted by a DFA and we are going to learn it later. So we are not going to go any further on this problem here.

Answer 2

Answer:

The non-acceptance of language by FA is​ called rejected state.

Explanation:

Finite Automata

A finite automata is a machine that has a finite number of states and it changes the state on a specific input.

We start from the initial state and by changing the states through the input reach the final state.

But some inputs are not accepted by finite automata and those are called rejecting states.

For example:

Let's say We have finite automata that accept only those strings that start with the 'A' letter. Any other string which does not start with 'A' letter will be rejected by the automata.

There are two types of FA:

1. DFA: DFA stands for Deterministic Finite Automata. It is called deterministic because it can change one state on one input.
2. NDFA: NDFA stands for Non-Deterministic Finite Automata. It is called non-deterministic because it can go to multiple states on the same input.

#SPJ3