Formal Language and Automata Theory notes f (1).pdf Flashcards
What is automata theory?
The basis for the theory of formal languages.
Define a symbol in the context of automata theory.
A character, an abstraction that is meaningless by itself.
What is an alphabet?
A finite set of symbols.
What is a word in automata theory?
A finite string of symbols from a given alphabet.
Define a language in automata theory.
A set of words formed from a given alphabet.
What operations can be performed on formal languages?
- Union
- Intersection
What are the three ways formal languages are defined?
- Regular expressions
- Standard automata
- Formal grammar system
What is the most general and powerful automaton?
The Turing machine.
List the four major families of automata.
- Finite-state machine
- Pushdown automata
- Linear-bounded automata
- Turing machine
What defines a finite-state machine (FSM)?
An automaton in which the state set Q contains only a finite number of elements.
Who were the first to present a description of finite automata?
Warren McCulloch and Walter Pitts in 1943.
What distinguishes a Mealy machine from a Moore machine?
A Mealy machine determines its outputs through the current state and the input, while a Moore machine’s output is based upon the current state alone.
Define the state transition function of a finite-state machine.
A function which maps an ordered sequence of input events into a corresponding sequence or set of output events.
What is a trap state in finite-state machines?
A state where no further input affects the outcome.
What is the formal definition of a finite automaton?
A 5-tuple (Q, Σ, δ, q0, F) where Q is the set of states, Σ is the input alphabet, δ is the transition function, q0 is the initial state, and F is the set of accepting states.
What does DFA stand for?
Deterministic Finite Automata.
What is the characteristic of a deterministic finite automaton (DFA)?
There is only one path for specific input from the current state to the next state.
True or False: DFA can accept the null move.
False.
What is the graphical representation of a DFA called?
State diagram.
What does the initial state of a DFA represent in a state diagram?
Marked with an arrow.
How can you describe the transition function of a DFA?
δ: Q x Σ → Q.
What is the significance of accepting states in finite automata?
If the input string ends in an accepting state, the input is considered accepted.
Fill in the blank: A finite automaton accepts or rejects an input based on a defined set of strings known as the _______.
[language of the automaton]
What is an example of a finite automaton application?
Airplane safety control.
What is the mathematical representation of a finite automaton?
Q, Σ, δ, q0, F.
What is the initial state of a DFA when given input 0?
The DFA changes state to q1.
What type of strings can a DFA accept?
Any string which ends with 0.
What type of strings will a DFA reject?
Any string which ends with 1.
What is the 5-tuple representation of an NDFA?
(Q, ∑, δ, q0, F)
What does Q represent in the NDFA definition?
A finite set of states.
What does ∑ represent in the NDFA definition?
A finite set of symbols called the alphabets.
What is the transition function δ in an NDFA?
δ: Q × ∑ → 2Q.
What does q0 signify in the NDFA definition?
The initial state from where any input is processed.
What does F represent in the NDFA definition?
A set of final state/states of Q.
How is an NDFA graphically represented?
By digraphs called state diagrams.
What do the vertices represent in an NDFA state diagram?
The states.
How are transitions indicated in an NDFA state diagram?
By arcs labeled with an input alphabet.
What indicates the initial state in an NDFA diagram?
An empty single incoming arc.
What indicates the final state in an NDFA diagram?
Double circles.
What is a key difference between DFA and NDFA regarding transitions?
DFA transitions to a single state; NDFA can transition to multiple states.
Can empty string transitions be seen in DFA?
No, they are not permitted.
What is the condition for a string to be accepted by a DFA or NDFA?
It ends in an accepting state after reading the string wholly.
What is the language L accepted by DFA/NDFA?
{S | S ∈ ∑* and δ*(q0, S) ∈ F}
What does L’ represent in relation to DFA/NDFA?
The complement of accepted language L.
What strings does the DFA accept based on the example provided?
{0, 00, 11, 010, 101, …}
What strings does the DFA reject based on the example provided?
{1, 011, 111, …}
What is one of the examples of a DFA design?
Accept strings that start with 1 and end with 0.
What is the regular expression for the set of strings that end in 3 consecutive 1’s?
(0 | 1)* 111
What is the union operator in regular expressions?
R1 | R2 or R1 U R2.
What does the concatenation operator do in regular expressions?
R1R2 combines patterns from R1 and R2.
What does the Kleene closure operator represent?
R1* includes epsilon, L(R1), and all concatenations of R1.
What is the language of the regular expression (0 + 10*)?
{0, 1, 10, 100, 1000, …}
What does the regular expression (a+b)* represent?
Set of strings of a’s and b’s of any length including the null string.
What does the regular expression (11)* represent?
Set consisting of even number of 1’s including empty string.
What is the property that states the union of two regular sets is regular?
Property 1.
What is an example of a regular expression that denotes an empty language?
φ
What does ε represent in regular expressions?
The language containing an empty string.
What is the language represented by the regular expression (aa)(bb)b?
Strings consisting of even number of a’s followed by odd number of b’s.
What is the set L1 in the context of regular expressions?
{ a, aa, aaa, aaaa, ….} (Strings of all possible lengths excluding Null)
What is the set L2 in the context of regular expressions?
{ ε, aa, aaaa, aaaaaa,…….} (Strings of even length including Null)
What is the result of the intersection L1 ∩ L2?
{ aa, aaaa, aaaaaa,…….} (Strings of even length excluding Null)
What is the regular expression for the intersection of L1 and L2?
RE (L1 ∩ L2) = aa(aa)*
What is the complement of a regular set?
All strings that are not in the set
What is the regular expression for the complement of the set L?
RE (L’) = a(aa)*
What does the difference of two regular sets represent?
Strings in the first set that are not in the second set
What is the regular expression for the difference L1 – L2?
RE (L1 – L2) = a (aa)*
What is the property of the reversal of a regular set?
The reversal of a regular set is also regular
What is the regular expression for the reversal LR of the set L?
RE (LR) = 01 + 10 + 11 + 10
What is the closure of a regular set?
The set formed by concatenating the regular set with itself zero or more times
What is the regular expression for the closure of the set L?
RE (L) = a (a)
What is a pushdown automaton (PDA)?
A mathematical model that extends finite automata with a stack for memory
What are the seven tuples that define a PDA?
M = (Q, ∑, Γ, δ, q0 , z0, F)
What does ‘Q’ represent in the context of a PDA?
A finite set of states
What does ‘∑’ represent in the context of a PDA?
A finite set of input alphabet/symbols
What does ‘Γ’ represent in the context of a PDA?
A finite stack alphabet
What is the transition function ‘δ’ in a PDA?
It governs the behavior of the automaton, mapping state/input/stack symbol to new state/stack operation
What is the initial state ‘q0’ in a PDA?
The state before making any transitions
What does ‘z0’ represent in a PDA?
The stack start symbol
What is meant by the term ‘Instantaneous Description’ in a PDA?
A triplet (q, w, s) representing the state, unconsumed input, and stack contents
What does the turnstile notation represent in PDA transitions?
It connects pairs of IDs representing transitions
What is one application of finite automata?
Recognizing patterns in text or data
How are finite automata used in programming languages?
To implement regular expressions
What is one application of pushdown automata?
Parsing context-free grammars
What do pushdown automata model in natural language processing?
They recognize and parse sentences
True or False: A pushdown automaton can read an input symbol in every transition.
False
Fill in the blank: A PDA has a stack with _______ size.
infinite
