answersLogoWhite

0

The defining characteristic of FA is that they have only a finite number of states. Hence, a finite automata can only "count" (that is, maintain a counter, where different states correspond to different values of the counter) a finite number of input scenarios.

There is no finite automaton that recognizes these strings:

  • The set of binary strings consisting of an equal number of 1's and 0's
  • The set of strings over '(' and ')' that have "balanced" parentheses

The 'pumping lemma' can be used to prove that no such FA exists for these examples.

User Avatar

Wiki User

13y ago

What else can I help you with?

Continue Learning about Engineering

What is the difference between deterministic finite automata and non deterministic finite automata?

A deterministic Finite Automata)DFA will have a single possible output for a given input.The answer is deterministic because you can always feel what the output will be.A (Nondeterministic Finite Automata)NFA will have at least one input which will cause a "choice" to be made during a state transition,unlike a (deterministic Finite Automata)DFA one input can cause multiple outputs for a given (Nondeterministic Finite Automata)NFA.


Describe how lexical analyzer generators are used to translate regular expressions into deterministic finite automata?

Lexical analyzer generators translate regular expressions (the lexical analyzer definition) into finite automata (the lexical analyzer). For example, a lexical analyzer definition may specify a number of regular expressions describing different lexical forms (integer, string, identifier, comment, etc.). The lexical analyzer generator would then translate that definition into a program module that can use the deterministic finite automata to analyze text and split it into lexemes (tokens).


Who invented the automata?

the greeks


What is the difference between automata and automaton?

automata is simply plural of automaton. shantanu sharma SCRIET 2008-2012


Difference between deterministic finite automaton and non deterministic finite automaton?

The state machine described in the previous section is a deterministic finite automaton, in which each state is unique. What would make a finite automaton nondeterministic is if each state was not. For the example, if the state machine allowed the input to have any letter as the second letter for the word "person" to transition to the next, then the next state would not be unique, making it a nondeterministic finite automaton.

Related Questions

What is full form of DFA and NFA?

DFA - deterministic finite automata NFA - non-deterministic finite automata


What is the difference between deterministic finite automata and non deterministic finite automata?

A deterministic Finite Automata)DFA will have a single possible output for a given input.The answer is deterministic because you can always feel what the output will be.A (Nondeterministic Finite Automata)NFA will have at least one input which will cause a "choice" to be made during a state transition,unlike a (deterministic Finite Automata)DFA one input can cause multiple outputs for a given (Nondeterministic Finite Automata)NFA.


Are all deterministic finite automata (DFAs) also non-deterministic finite automata (NFAs)?

No, not all deterministic finite automata (DFAs) are also non-deterministic finite automata (NFAs). DFAs have a single unique transition for each input symbol, while NFAs can have multiple transitions for the same input symbol.


What is difference between finite state automaton and transition graph?

finite automata


Is it possible to show that all deterministic finite automata (DFA) are decidable?

Yes, it is possible to show that all deterministic finite automata (DFA) are decidable.


What does dfa stand for?

Deterministic finite state automata


What is dfa and nfa?

DFA - Deterministic Finite Automata NFA - Non-Deterministic Finite Automata Both DFAs and NFAs are abstract machines which can be used to describe languages.


What is better Finite Automata or Regular Expression?

Finite Automata and Regular Expressions are equivalent. Any language that can be represented with a regular expression can be accepted by some finite automaton, and any language accepted by some finite automaton can be represented by a regular expression.


Is it possible to demonstrate that all deterministic finite automata (DFA) are in the complexity class P?

Yes, it is possible to demonstrate that all deterministic finite automata (DFA) are in the complexity class P.


What you mean by Finite Automata?

Finite automata are machines used to recognize patterns from input set of characters. They either reject or accept inputs based on the already defined pattern set by the FA.


Define the languages accepted by NFA and DFA?

In general, finite state machines can model regular grammars. Deterministic finite automata can represent deterministic context-free grammars. Non-deterministic finite automata can represent context-free grammars.


What is the FA?

The Football Association. Simple! wrong....... F A Means finite automata......