The course introduces some fundamental concepts in automata
theory and formal languages including grammar, finite automaton, regular
expression, formal language, pushdown automaton, and Turing machine. Not only
do they form basic models of computation, they are also the foundation of many
branches of computer science, e.g. compilers, software engineering, concurrent
systems, etc. The properties of these models will be studied and various
rigorous techniques for analyzing and comparing them will be discussed, by
using both formalism and examples.
QUESTIONS | ANSWERS |
---|---|
TRUE | An alphabet is any finite set of symbols. |
Leaves | Labeled by a terminal symbol or ε. |
S & A | Non-terminal symbols |
Type-0 grammars | IT generate recursively enumerable languages. The productions have no restrictions and phase structure grammar including all formal grammars. They generate the languages that are recognized by a Turing machine. |
w | Unconsumed input. |
Accept | Finite Automata all regular languages and only regular languages. |
TRUE | Z2 uses electricity to convey letters and transmit information quickly in 1844. |
P | S → aAb, aA →aaAb, A→ε |
alphabet | A formal language is a set of strings, each string composed of symbols from a finite set called |
((a.b)+c)* | Having the initial state as a final state, give the deterministic finite state automaton that accepts the regular expression. |
1956 | Noam Chomsky gave a mathematical model in ___ which is effective for writing computer languages. |
F | A set of accepting states (F ∈ Q) |
F | Set of final or accepting states |
Assembly Language | An English like abbreviations representing elementary computer operations. |
Parse Tree | A of a derivation is a tree in which each internal node is labeled with a nonterminal. |
union | The _____ of two sets A and B is the set containing those elements which are elements of A or elements of B. |
No state p has two outgoing transitions | A DPDA is a PDA in which. |
Regular | If L1 and L2 are regular sets then intersection of these two will be |
Parse Tree | An order rooted tree that graphically represents the semantic information a string derived from a context-free grammar. |
FALSE | Turing hypothesis believed that a function is said to be computable if and only if it can be computed by a Turing machine. |
δ | A transition function: Q × (Σ∪{ε}) × S × Q × S* |
F | A set of accepting states (F ∈ Q). |
S | The start symbol. |
Answer | QUESTIONS |
NDFA | A string is accepted by a, iff the DFA/NDFA starting at the initial state ends in an after reading the string. |
w | The unconsumed input |
accepted, generated | Context-free grammars are more expressive than finite automata; if a language L is _____ by a finite automata then L can be _______ by a context-free grammar. |
Derivation tree | An order rooted tree that graphically represents the semantic information a string derived from a context-free grammar. |
Type-0 grammars | IT generate recursively enumerable languages. The productions have no restrictions and phase structure grammar including all formal grammars. |
Type-2 grammars | It generate context-free languages. The productions must be in the form A → γ |
TRUE | Are ambiguous grammar context free? |
a,b | The language L contains all strings over the alphabet {a,b} that begin with and end with |
Minimizing False Positive | Increasing accuracy, or precision. |
ϵ | Regular expression Φ* is equivalent to |
computer | A general purpose, programmable, information processor with input and output. |
Σ | Is a finite set of symbols called the alphabet. |
current state, unprocessed input, stack content | A PDA machine configuration (p, w, y) can be correctly represented as ____________ . |
S | Start symbol, S ∈ N |
3 | Number of states require to accept string ends with 10. |
TRUE | The tape head is positioned at one of the tape cells for scanning the input symbol from the input tape and initially the tape head points at the left most cell of the input tape. |
bottom-up approach | * Starts from tree leaves. It proceeds upward to the root which is the starting symbol S |
Noam Chomsky, 1956 | The theory of formal languages finds its applicability extensively in the fields of Computer Science. gave a mathematical model of grammar in which is effective for writing computer languages. |
{0a1b|a=2,b=3} | Which among the following is the correct option for the given grammar? G->X111|G1,X->X0|00. |
Process | The following are phases of C++ Programs except |
Regular Expressions | A compact textual representation of a set of strings representing a language. |
top-down parser | A parsing that starts from the top with the start-symbol and derives a string using a parsetree. |
Regular | If L1 and L2 are regular sets then intersection of these two will be. |
ENIAC | One of the first programmable electronic computers in 1945. |
Parsing | Is used to derive a string using the production rules of a grammar. |
PDA | A _____ may or may not read an input symbol, but it has to read the top of the stack in every transition |
1936 | In _____ Allan M. Turing proposed the Turing machine as a model of "any possible computation". |
δ | __ is the transition function where δ: Q × Σ → Q. |
Q | A finite number of states |
Single Move | The of a Turing machine depends on the current state of finite control and the tape symbol present in the input tape. |
Output Alphabet | Which of the following is a not a part of 5-tuple finite automata? |
Accepted by DFA | A language is regular if and only if. |
I | The initial stack top symbol (I ∈ S) |
Minimizing False Negative | Increasing coverage, or recall. |
Computer | Which one is the answer? |
TRUE | For every pair of regular expressions R and S, the languages denoted by R(SR)* and (RS)*R are the same. |
L1=L2 | Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then. |
q0 | An initial state q0 ∈ Q. |
Reduction of CFG | Elimination of productions and symbols is called simplification of CFGs. Simplification essentially comprises of the following steps: |
Null Move | A Finite Automaton with null moves (FA-ε) does transit not only after giving input from the alphabet set but also without any input symbol. This transition without input is called a. |
rinse, lather, repeat | An algorithms to shampoo your hair. |
s | The stack contents. |
F | Set of final or accepting states. |
Q | Finite set of states. |
(a+b)* | A set of strings of a's and b's of any length including the null string. So L= { ε, a, b, aa , ab , bb , ba, aaa.......}, the regular |
q0 | An initial state q0 ∈ Q |
Living Organisms | It process information in their efforts to eat, survive, and reproduce. |
Transducer | An automaton that produces outputs based on current input and/or previous state is called. |
State Diagram | A DFA is represented by digraphs called. |
LIFO, finite | The PDA has infinite memory and access in _____ order and the finite automata has ____ memory. |
Σ | A finite set of input symbols. |
A | What is the final result after converting the following NFA-ε to NFA without Null move. |
q | The state. |
Partial Derivation Tree, Sub-Tree | A sub-tree of a derivation tree/parse tree such that either all of its children are in the sub-tree or none of them are in the |
q0 | Starting state |
ϵ | Regular expression Φ* is equivalent to. |
No state p has two outgoing transitions | A DPDA is a PDA in which |
Q | A finite set of states. |
TRUE | For a regular expression 'a', we can construct the following FA: |
TRUE | A grammar G is ambiguous if there is a word w Î L(G) having are least two different parse trees. |
F | __ is a set of final state/states of Q (F ⊆ Q). |
Bottom-Up Approach | * Starts from tree leaves. It proceeds upward to the root which is the starting symbol S. |
1936 | In ____ Allan M. Turing proposed the Turing machine as a model of "any possible computation". |
F | A set of final state/states of Q (F⊆Q). |
T | A set of terminals where N ∩ T = NULL. |
1936 | In Allan M. Turing proposed the Turing machine as a model of "any possible computation". |
What is the final result after converting the following NFA-ε to NFA without Null move. | |
I | The initial stack top symbol (I ∈ S). |
Q | Is a finite set of states. |
PDA | A may or may not read an input symbol, but it has to read the top of the stack in every transition |
Σ | Finite set of input alphabets |
Charles Babbage | Who is the father of modern computer? |
Alphabet | A formal language is a set of strings, each string composed of symbols from a finite set called. |
Time Complexity | It refers to the measure of the number of times the tape moves when the machine is initialized for some input symbols and the space complexity is the number of cells of the tape written. |
Push the current input symbol into the stack., Replace the right‑hand side of a production at the top of the stack with its left‑hand side. , If the top of the stack element matches with the current input symbol, pop it. , If the input string is fully read and only if the start symbol 'S' remains in the stack, pop it and go to the final state . | For bottom-up parsing, a PDA has the following four types of transitions: |
s | The stack contents |
TRUE | There are 5 tuples in finite state machine. |
δ | A transition function δ : Q × (Σ ∪ {ε}) → 2Q. |
ababaabaa | Which of the following will not be accepted by the following DFA? |
w | The unconsumed input. |
Transitive and Reflexive | |-* is the closure of |- |
3 | The minimum number of states required to recognize an octal number divisible by 3 are/is. |
N | A set on non-terminal symbols. |
Stack | The transition a Push down automaton makes it additionally dependent upon the |
q | The state |
w | Unconsumed input |
Top-Down Approach | * Starts with the starting symbol S. It goes down to tree leaves using productions. |
Current state, Unprocessed input, Stack content | A PDA machine configuration (p, w, y) can be correctly represented as. |
Grammar | The entity which generate Language is termed as: |
TRUE | A PDA accepts a string when, after reading the entire string, the PDA is in a final state. |
Analytic Engine | A conceptual design for a machine consisting of a Mill, Store, Printer, and Readers. |
Mathematics | Computer science has roots in two fields : |
Vertex | Labeled by a non-terminal symbol. |
finite control, input tape | The basic model of a Turing machine consists of _______ and _______ , in which the finite control has finite set of states and the transition between the states. |
Σ | Empty string |
Σ * | It is a unary operator on a set of symbols or strings, that gives the infinite set of all possible strings of all possible lengths. |
End Symbol | Which among the following is not a part of the Context free grammar tuple? |
transitive and reflexive | |-* is the _____ closure of |- |
FALSE | A regular expression consisting of a finite set of grammar rules is a quadruple. |
Q | __ is a finite set of states. |
TRUE | For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa |
Σ | A stack symbols |
Γ | Set of all tape symbols |
Accepted | Context-free grammars are more expressive than finite automata; if a language L is by a finite automata then L can be blank by a context-free grammar. |
δ | Transition function |
q0 | Is the initial state from where any input is processed (q0 ∈ Q). |
(a+b)* | A set of strings of a's and b's of any length including the null string. So L= { ε, a, b, aa , ab , bb , ba, aaa.......}, the regular expression is. |
None of the mentioned | Number of final state require to accept in minimal finite automata. |
q0 | __ is the initial state from where any input is processed (q0 ∈ Q). |
Start State | Identify the modeling recognition of the word "then" |
Δ | Blank symbol |
L is a set of 0n1n | Which among the following cannot be accepted by a regular grammar? |
single move | The __________ of a Turing machine depends on the current state of finite control and the tape symbol present in the input tape. |
TRUE | For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa. |
Alan Turing | Who is the father of modern computer science? |
FALSE | Any set that represents the value of the Regular Expression is called a Property set. |
{3,6} | If A = {3, 4, 6, 8} and |
Type-0 grammars | T generate recursively enumerable languages. The productions have no restrictions and phase structure grammar including all formal grammars. |
Q | A finite number of states. |
Accepted, Ignored | Context-free grammars are more expressive than finite automata; if a language L is by a finite automata then L can be by a context-free grammar. |
TRUE | The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable. |
Abacus | The first counting machine developed 5000 years ago in the Middle East. |
Context Sensitive Language | Production Rule: aAb->agb belongs to which of the following category? |
Bottom-Up Parser | It starts from the bottom with the string and comes to the start symbol using a parse tree. |
predicates | are parameterized statement, they are true or false depending on the values of their parameters. |
Parsing | ______ is used to derive a string using the production rules of a grammar. |
q0 | The initial state (q0 ∈ Q) |
TRUE | Every context free grammar can be transformed into an equvalent non deterministic push down automata. |
complement | A language accepted by Deterministic Push down automata is closed under which of the following? |
Root Vertex | Labeled by the start symbol. |
Pumping Lemma | Is to be applied to show that certain languages are not regular. It should never be used to show a language is regular. |
6 | A Moore machine can be described by a tuple. |
Push the current input symbol into the stack. | For bottom-up parsing, a PDA has the following four types of transitions: |
FALSE | Leibniz introduced binary notation of calculation. |
a & b | Terminal symbols |
David Hilbert | challenged the mathematical community to find an infallible, mechanical method for constructing and checking truth of mathematical statements. |
3,6,2,5,4 | For the given Regular expression, the minimum number of terminals required to derive its grammar (011+1)*(01)* is |
Null Move | A Finite Automaton with null moves (FA-ε) does transit not only after giving input from the alphabet set but also without any input symbol. This transition without input is called a |
δ | Is the transition function where δ: Q × Σ → Q. |
Minimizing False Negatives | Increasing coverage, or recall. |
Q | Finite set of states |
Σ | Finite set of input alphabets. |
Root with no children is called a leaf | Which of the following statement is false in context of tree terminology? |
Push | A new symbol is added at the top. |
PDA | A DFA can remember a finite amount of information, but a ____ can remember an infinite amount of information. |
1956 | Noam Chomsky gave a mathematical model in which is effective for writing computer languages. |
Every CFG for L is ambiguous | Which of the following statements are correct for a concept called inherent ambiguity in CFL? |
TRUE | Any production rule in the form A → B where A, B ∈ Non-terminal is called unit production. |
TRUE | Regular sets are closed under union,concatenation and kleene closure. |
Minimizing False Positives | Increasing accuracy, or precision. |
Unit Production | Any production rule in the form A → B where A, B ∈ Non-terminal is called. |
PDA | A DFA can remember a finite amount of information, but a can remember an infinite amount of information. |
Production | Is used to derive a string using the production rules of a grammar. |
Q | A finite set of states |
FALSE | The entity which generate Language is termed as regular languages. |
TRUE | A pushdown automaton is a way to implement a context-free grammar in a similar way to design DFA for a regular grammar. |
Pop | The top symbol is read and removed. |
Minimizing False Positives | Increasing accuracy, or precision |
Top-Down Parser | It starts from the top with the start-symbol and derives a string using a parse tree. |
Go to bathroom | An algorithms to shampoo your hair. |
TRUE | Computers are general purpose because they can perform many different tasks. |
Σ | __ is a finite set of symbols called the alphabet. |
FALSE | The complement of an infinite language is necessarily finite. |
F | Is a set of final state/states of Q (F ⊆ Q). |
Context | A right-most derivation of a sentential form is one in which rules transforming the are always applied. |
P | A set of rules, P: N → (N U T)*, it does have any right context or left context. |
δ | A transition function: Q × (Σ∪{ε}) × S × Q × S*. |
PDA | A may or may not read an input symbol, but it has to read the top of the stack in every transition. |
Pascaline | The first mechanical calculator using gears for calculation developed in 1642. |
Statement 1 is false, Statement 2 is true | According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F} Statement 1: q ϵ Q'; Statement 2: FϵQ |
stack | The transition a Push down automaton makes it additionally dependent upon the _____. |
parse tree | A __________ of a derivation is a tree in which each internal node is labeled with a nonterminal. |
s | The stack content |
7 | The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is |
1956 | Noam Chomsky gave a mathematical model in _______ which is effective for writing computer languages. |
FALSE | Language may be derived from other strings using the productions in a grammar. |
{ 4,6} | If A = {3, 4, 6, 8} and |
Context sensitive language is a subset of context free language | Which of the following statement is false? |
True | Global Positioning System (GPS) calculates latitude and longitude from satellite signals. |