Karteikarten
CH1 : Gems
Karten in diesem Stapel (25)
- 1- Now how to define a language and how to specify an algorithm to recognize themsimply listing all of its strings, and then the list is 'hardcoded' into a recognition algorithm (or 'hard-wired' into the machine)
- 2Define: what is computation?Computation can be defined as finding a solution to a problem from the given inputs by means of an algorithm.
- 3language definition Falls into three broad categories?1. **Algebraic definition**
# Languages are defined by expressions, specifying how they are built up from a finite set of simple language using various operations combining languages
======================
2. **Grammars**
# These can be understood as algorithms for generating languages for listing all (and only) the strings in the language
======================
3. **Automata**
# These are simply abstract models of computers, specialized to recognize particular languages. - 4Define: what is computation?finding a solution to a problem from the given inputs by means of an algorithm
- 5Define : Theory of computation?a subfield of computer science and mathematics,
deals with finding solutions to problems from the given inputs - 6Model of computation?Model of computation means a formal, abstract definition of a computer
- 7what are the types of computation models?1. FSM
2. RAM
3. TM
2. Parraller model
1. multiprocessor model
2. work-depth model - 8Define : abstraction ?Abstraction means a processor design which is not intended to be implemented as hardware but its notional executor of a particular intermediate language used in a compiler or interprete
- 9Define : Abstract Machineis a procedure for executing a set of instructions in some formal
language, - 10Define : automataAn automaton (plural: automata) is self-operating machine
- 11FSM counting to Five?
- 12Define : Finite State Machine?is a machine, or a mathematical model of a machine, which can only reach a finite number of states and transitions
- 13Finite state components?- a Control Unit
- a Read Unit, and
- an Input Tape (or input file) - 14Define : State ?A state is a complete set of properties, transmitted by an object to an observer via one or more channels
- 15Transition Represented by :- State diagram or Transition diagram
- State transition table
- Transition functions - 16State Diagram from transition table?Step-1: **Draw the circles to represent the states given**.
Step-2: For each of the states, scan across the corresponding row and **draw an arrow to the destination state**(s). There can be multiple arrows for an input character, if the automaton is an NFA.
Step-3: Designate a state as the **start state**. The start state is given in the formal definition of the automata.
Step-4: Designate one or **more states as the accept state. - 17Mathematical Representation of Finite State Machine
- 18EX: 1.Define computation. Explain the different computational models?**Computation can be defined as finding a solution to a problem from the given inputs by means of an algorithm.**
types of computation models?
1. Serial model
1. FSM
2. RAM
3. TM
2. Parraller model
1. multiprocessor model
2. work-depth model - 19EX 2.What is a Finite State Machine? Explain with examples?-is a machine, or a mathematical model of a machine, which can only reach a finite number of states and transitions.
- 20EX 4.Explain, using a diagram, the elements of Finite State System1. states which define the behavior and may produce actions
2. state transitions
3. rules or conditions
4. input events
5. current state
6. current input symbol
7. the information currently present in the temporary storage - 21EX 5.What is a transition? Explain, with examples, the different symbols used in a state transition diagram?# A Transition is the act of passing from one state/place to the next.
## b. A change from one place or state or subject or stage, to another
- 22Ex 6.Give the general procedure for drawing a state diagram from transition table**Step-1** Draw the circles to represent the states given.
**Step-2**: For each of the states, scan across the corresponding row and draw an arrow to the destination state(s). There can be multiple arrows for an input character, if the automaton is an NFA.
**Step-3**: Designate a state as the start state. The start state is given in the formal definition of the automata.
**Step-4**: Designate one or more states as the accept state. - 237.Explain the advantages and
- 24disadvantages of automata
- 25uses
Informationen
- Beschreibung
- Medium Computational Theory Karteikarten am CH1 : Gems, erstellt von Amjed omaF am 19/12/2022.
- Erstellt von
- Amjed omaF
- Aufrufe
- 1
- Bewertung