Ch 8. Key Terms

Accepting State: A state of a finite state machine such that, if the machine finishes processing an input string in that state, the string is considered accepted.

Alphabet: A finite set of symbols from which strings in a formal language are constructed.

Automaton: A mathematical model used to represent systems that process input strings by transitioning between states according to defined rules.

Backus-Naur Form (BNF): A formal notation used to describe the syntax of languages by specifying production rules that define how valid strings are formed.

Context-Free Grammar: A grammar in which each production rule replaces a single non‑terminal symbol, independently of its surrounding symbols.

Context-Sensitive Grammar: A grammar in which production rules depend on the symbols surrounding the symbol being replaced.

Derivation: A sequence of steps showing how a string is generated from the start symbol by repeatedly applying production rules.

Deterministic Finite Automaton (DFA): A finite state automaton in which, for each state and input symbol, there is exactly one defined transition.

Finite State Machine (FSM): A computational model consisting of a finite set of states, an input alphabet, a transition function, a start state, and one or more accepting states.

Formal Language: A set of strings over a given alphabet that is defined by precise and unambiguous rules.

Grammar: A collection of production rules that define how strings in a formal language can be generated.

Input String: A finite sequence of symbols from an alphabet that is processed by a finite state machine or automaton.

Interactive Grammar: A grammar in which external inputs or environmental conditions can influence how production rules are applied during derivation.

Language: Any subset of [latex]\Sigma^{*}[/latex], representing a set of valid strings over an alphabet.

Non-Deterministic Finite Automaton (NFA): A finite state automaton that allows multiple possible transitions for the same input symbol and may include transitions that consume no input.

Output String: A sequence of symbols produced by a finite state transducer as it processes an input string.

Production Rule: A rule in a grammar that specifies how one symbol or group of symbols can be replaced by another sequence of symbols.

Regular Grammar: A restricted type of grammar that generates regular languages, which can be recognized by finite automata.

Regular Language: A language that can be recognized by a finite state automaton.

Start State: The state in which a finite state machine begins processing an input string.

Start Symbol: The designated symbol in a grammar from which all derivations begin.

State: A configuration of a finite state machine that determines how the next input symbol will be processed.

String: A finite sequence of symbols taken from an alphabet.

Transition Diagram: A graphical representation of a finite state machine showing states as nodes and transitions as directed edges.

Transition Function: A rule that specifies how a finite state machine moves from one state to another based on the current state and input symbol.