Does the empty string match the regular expression |y+a|?
- AYes
- BNo
y+a matches only the one-letter strings y and a.
Syllabus: lectures 25–45. Past-paper MCQs are shown first.Syllabus: lecture 25–45. Past paper ki MCQs pehle dikhai gayi hain.
285 MCQs · 208 short · 21 long questions · 285 MCQs from past papers285 MCQs · 208 short · 21 long sawal · 285 MCQs past papers se
Does the empty string match the regular expression |y+a|?
y+a matches only the one-letter strings y and a.
Which of the following statement is true about NFA with Null String?
An NFA-Λ may move along Λ-edges without reading input.
The strings or words which do not belong to a language is called ________ of that language
Strings not in L form the complement of L.
Even-palindrome is a ________ language.
Even-length palindromes need unbounded memory to match the two halves, so no FA accepts them.
Which of the following is NOT a regular language?
All three languages fail the pumping lemma, so none is regular.
Set of all palindromes over {a,b} is regular
PALINDROME fails the pumping lemma, so it is nonregular.
a^n b^n generates the ________ language
a^n b^n is nonregular; it is only a subset of EQUAL, not EQUAL itself.
For a non regular language there exist ________ FA
A language accepted by an FA is regular, so a nonregular language has no FA.
A non regular language can be represented by
RE, FA and TG all describe only regular languages.
Any language that can not be expressed by a RE is said to be regular language.
A language with no RE is nonregular.
The language that can be expressed by any regular expression is called a Non regular language.
A language with an RE is regular.
Set of all palindromes over {a,b} is:
PALINDROME fails the pumping lemma, so it is nonregular.
For a non regular language there exist …… FA:
No FA accepts a nonregular language.
A language of strings of prime length is considered to be:
PRIME is shown nonregular with the pumping lemma: pumping changes the length to a non-prime.
Let L be an infinite language accepted by a finite automaton with N states, then for all words W in L that have length more than N there are strings x,y and Z (y being non null string) and length(x)+length(y)≤N s.t. W=xyz and all strings of the form xy^n z are in L for n=1,2,3………..
This is pumping lemma version II.
For FA corresponding to (L1∩L2c)U(L1c∩L2) the regular expression can be determined that defines the language accepted by this :
The RE is found for the language accepted by that FA.
In CFG, the symbols that can't be replaced by anything are called ________.
Terminals are the final letters of words and are never rewritten.
Left hand side of a production in CFG consists of:
Every CFG production rewrites exactly one nonterminal.
The symbols that cannot be replaced by anything are called terminals
Terminals are never rewritten.
CFG given S → bS | Sb | aa represents language
b's can be added on either side of the single aa, giving b*aab*.
In CFG, the symbols that cannot be replaced by anything are called
Terminals are never rewritten.
The grammatical rules which involves meaning of words are called:
Rules about meaning are semantics; rules about form are syntax.
The CFG S --> aSa | bSb | a | b | Λ represents the language
Adding the same letter on both sides around a, b or Λ builds every palindrome.
The major problem in the earliest computers was
The handout says early computers had trouble handling mathematical formulae, which led to grammars and parsing.
The production S --> SS | a | b | Λ can be expressed by RE
S can produce any sequence of a's and b's, including Λ.
"CFG" stands for ________
CFG means Context Free Grammar.
The high level language is converted into assembly language codes by a program called compiler.
A compiler translates high-level code into lower-level code.
Grammatical rules which involve the meaning of words are called ________
Rules about meaning are semantics.
Grammatical rules which do not involve the meaning of words are called ________
Rules about form only are syntactic rules.
The symbols that must be replaced by other things are called ________
Nonterminals must be rewritten before a word is reached.
The grammatical rules are often called ________
Grammar rules are called productions.
The terminals are designated by ________ letters, while the non-terminals are designated by ________ letters.
By convention terminals are lowercase and nonterminals uppercase.
The language generated by ________ is called Context Free Language (CFL).
A CFL is the language generated by a CFG.
Σ = {a,b} Productions S → XaaX, X → aX, X → bX, X → Λ. This grammar defines the language expressed by ________
X generates (a+b)*, so XaaX gives (a+b)*aa(a+b)*.
Consider the Following CFG: (NOTE: Λ means NULL) S->Xa X->aX|bX|Λ above given CFG can be represented by RE
X gives (a+b)*, followed by a final a.
The langue generated by CFG is called Context free language (CFL)
A CFG generates a context free language.
The symbols that can't be replaced by anything are called -----------------
Terminals cannot be replaced.
S → aXb|bXa X → aX|bX|Λ The given CFG generates the language of strings in English
Words are a…b or b…a.
One language can have ……… CFG(s)
A CFL has at least one (in fact many) CFGs.
The language generated by the CFG is called the language ……by the CFG
It is the language produced (generated) by the CFG.
In CFG, the symbols that cannot be replaced by anything are called:
Terminals cannot be replaced.
The production S --> SS | a | b | Λ can be expressed by RE:
It generates (a+b)* (including Λ), which is not listed.
The same non terminals can be written in single line if they have more than one..........
Productions with the same left side can be combined with |.
There is at least one production that has one........on its left side:
A CFG has at least one production with the start non-terminal S on its left.
Left hand side of CFG may consist of:
One non-terminal on the left side.
The language generated by CFG is called ________.
By definition the language generated by a context free grammar is a context free language.
Left hand side of a production in Context free grammar (CFG) consists of ________.
In a CFG every production has exactly one nonterminal on its left side.
Syntax tree or Generation tree or Derivation tree are same tree
These are three names for the same tree that shows a derivation.
A Total Language Tree has
The total language tree of a CFG shows every derivation, so its leaves are all words of that one language.
The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .
Ambiguity is a property of a CFG.
The CFG is said to be ambiguous if there exists atleast one word of its language that can be generated by the different production trees,
That is the definition of ambiguity.
Consider the following CFG S→aS|bS|aaS|Λ it can be observed that the word aaa can be derived from more than:
aaa has several trees (a·a·a, aa·a, a·aa), so it has more than one production tree.
Any word generated by given CFG cannot also be expressed by Syntax tree or Generation tree or Derivation tree as well
Every derivation can be drawn as a tree.
In polish notation, (o-o-o) is the abbreviation of ________?
Polish (prefix) notation writes the operator before its two operands.
Which of the following is a regular Context Free Grammar:
In S → abS | baS | Λ each production is terminals followed by at most one nonterminal at the right end.
Semi-word is a string having some terminals and one non-terminal at the right of string.
A semiword is terminals followed by exactly one nonterminal at the end.
CFG may also represent a regular language.
Every regular language has a CFG (a regular grammar).
The language generated by that CFG is regular if ________
A CFG whose productions are all nonterminal → semiword or word is a regular grammar.
The CFG which generates the regular language is called
A CFG for a regular language in semiword form is a regular grammar.
The language generated by that CFG is regular if _________
If every production is non-terminal → semiword or non-terminal → word, the language is regular.
If every production in CFG is one of the following forms Nonterminal → semi word, Nonterminal → word. Then the language generated by that CFG is :
Such a grammar is a regular grammar, so the language is regular.
CFG is said to be a regular grammar if it generates the regular language i.e.a CFG is said to be a regular grammar in which each production is one of the:
Non-terminal → semiword or non-terminal → word.
In the null production N --> Λ, N is a
The left side of any CFG production is a nonterminal.
The production of the form: Nonterminal-> Λ is said to be ________ production
A production with Λ on the right is a null production.
If a CFG has a null production, then it is ________
Null productions can be removed, losing at most the word Λ.
The production of the form nonterminal → Λ is said to be null production.
This is the definition of a null production.
If a CFG has a null production, then it is possible to construct another CFG accepting the same language without null production
Null productions can be removed, except that the word Λ may be lost.
The production of the form no terminal → Λ is said to be null production.
Non-terminal → Λ is a null production.
A production is called null able production if it is of the form N → Λ
The handout counts N → Λ (or any derivation of Λ from N) as nullable.
If a CFG has only productions of the form nonterminal → string of two nonterminals or nonterminal → one terminal then the CFG is said to be in ________
These two production forms are exactly the definition of Chomsky Normal Form.
________ and ________ are removed in order to make a CFG in Chomsky Normal Form(CNF).
Converting to CNF first removes null productions and unit productions.
Identify the TRUE statement about following CFG: S -> SB|AB A -> CC B -> b C -> a
Every production is either two nonterminals or one terminal, so it is in CNF.
CNF is stands for
CNF means Chomsky Normal Form.
All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the :
A CNF grammar has no null productions, so only Λ is lost.
We can also represent an FA using different states e.g Accept state; Reject state, Read state etc. The ________ state behaves as final state of an FA
In the new format of an FA, reaching ACCEPT means the input is accepted, like a final state.
________ where the input string is placed before it is run, is called ________
The input string is written on the INPUT TAPE before the machine runs.
A read state can have ________ outgoing edge/ edges.
A READ state may branch on any number of letters, including blank.
Halt states are
The machine stops at ACCEPT or REJECT, so these are the halt states.
The input string is placed, before it runs, in
The input string is written on the input tape.
The locations into which we put the input letters on "Input Tape" are called ________
The input tape is divided into cells, one letter per cell.
________ states are called the halt states.
The machine stops at ACCEPT or REJECT.
The part of an FA, where the input string is placed before it is run, is called ________
The input string is written on the input tape.
In new format of an FA (discussed in lecture 37), This state is like dead-end non final state
REJECT halts without accepting, like a dead non-final state.
In new format of an FA This state is like dead-end non final state:
REJECT works like a dead-end non-final state.
Like TG, a PDA can also be non-deterministic
A PDA may have several edges with the same label from a READ or POP state.
A PDA is called nondeterministic PDA if ________
Nondeterminism means a choice of edges with the same label at a READ or POP state.
The PDA is called non-deterministic PDA when there are more than one out going edges from ________ state
Branching on the same label happens only at READ or POP states.
Identify the TRUE statement:
A PDA may be nondeterministic, just like a TG.
In nondeterministic PDA a string is supposed to be accepted, if there exists at least one path traced by the string, leading to ________ state.
A nondeterministic PDA accepts if some path reaches ACCEPT.
For every Context Free Grammar (CFG), we can make the corresponding ________ .
Every CFG can be converted into a PDA that accepts the same language.
Choice of path can be determined by left most derivation of the string belonging to CFL at ________ state
In the PDA built from a CFG the branching happens at the POP state, and the leftmost derivation picks the branch.
Language which are context –free are called Non –CFL:
Non-CFLs are languages that are not context free.
A nonterminal is said to be self-embedded, if in a given derivation of a word, it ever occurs as a tree ________ of itself.
A self-embedded nonterminal appears again below itself in the derivation tree, i.e. as its own descendant.
The process of finding the derivation of the word generated by particular grammar is called
Finding a derivation (parse tree) of a word in a grammar is called parsing.
Chomsky normal form (CYK) algorithm was proposed by ________ .
The CYK algorithm is named after Cocke, Younger and Kasami; John Cocke is the C.
The process of finding the derivation of word generated by particular grammar is called :
Finding a derivation is parsing.
CYK algorithm was invented by John Cocke and later was published by ____
The CYK algorithm is named after Cocke, Younger and Kasami; Tadao Kasami and Daniel H. Younger published it.
There are different parsing techniques, including ________
Top-down, bottom-up and the technique for arithmetic expression grammars are all parsing techniques.
CYK algorithm was invented by John Cocke and later was published by ____
The CYK algorithm is named after Cocke, Younger and Kasami; it was later published by Tadao Kasami and Daniel H. Younger.
An FSM can be considered as TM
An FSM reads its finite input once, left to right, without going back.
The above machine (edges labelled (a,a,R), (b,b,R)) is a/an ________
Edge labels of the form (read, write, move) belong to a Turing machine.
Who did not invent the Turing machine?
Alan Turing, A. M. Turing and Turing are the same person, who invented it.
Which statement is true?
A Turing machine has a tape that is infinite in one direction.
TM is more powerful than FSM because
The read-write tape gives a TM unlimited memory, which an FSM lacks.
What Turing Machine does not have?
A Turing machine has a tape and a read-write head but no stack.
A program which is the set of rules which show that which state is to be entered when a letter is read form the :
A TM program says which state to enter on reading a letter from the TAPE.
Can a turing machine's head ever be in the same location in two successive steps?
In this model the head moves one cell left or right on every step.
In ________ there are Finite set of states containing exactly one START state and some (may be none) HALT states that cause execution to terminate, when the HALT states are entered.
START and HALT states are part of the definition of a Turing machine.
If Σ = {aa, bb}, then Σ* will not contain
Every word of Σ* is built from blocks aa and bb, so it cannot contain an odd run like aaa followed by bbb.
"One language can have ________ TG's".
Many different TGs can accept the same language.
According to 1st part of the Kleene's theorem, If a language can be accepted by an FA then it can be accepted by a ________ as well.
Part I of Kleene's theorem states that every language accepted by an FA is accepted by a TG.
If L is a regular language then, Lc is also a ________ language.
Swapping final and non-final states of an FA for L gives an FA for its complement.
Pumping lemma is generally used to prove that:
Showing that some long word cannot be pumped proves that a language is not regular.
If the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will ________ word/words.
If an FA with N states accepts any word, it accepts one shorter than N, so none accepted means the language is empty.
Which of the following is a regular language?
Odd number of zeroes is accepted by a two-state FA, while the other two languages are nonregular.
Which of the following pairs of regular expressions are equivalent?
X*X+ needs at least one X and allows any number more, which is exactly X+.
An alphabet Σ is valid if
If no letter is the start of another letter, every string can be tokenized without ambiguity.
Which of the following statement is true
A Moore machine prints a character in the start state before reading input, so its output is one longer than the input.
Alphabet Σ = {a, bc, cc} has number of letters
The alphabet lists three letters: a, bc and cc.
If r1 is a regular expression then r1* is a ________
The Kleene star of a regular expression is again a regular expression by definition.
We cannot write regular expressions for all ________ .
Every FA, TG and NFA has an RE by Kleene's theorem, but some CFGs generate nonregular languages.
The language of Palindromes defined over an alphabet set {a, b} can be recognized by ________.
PALINDROME is nonregular but context free, so a PDA is needed.
(Σ* - L) represent the ________ of a language L.
All strings over Σ that are not in L form the complement of L.
If we have two transition graphs then their union will be expressed by
A new start state with Λ-edges to both old start states lets a word follow either TG.
If L1 and L2 are expressed by regular languages then L1 + L2 is also a ________ Language.
Regular languages are closed under union.
Finite Automation (FA) and Nondeterministic Finite Automation (NFA) are equivalent if
Two machines are equivalent when they accept the same language.
________ is always Deterministic.
An FA has exactly one transition for each letter from each state, so it is deterministic.
If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by
The expression is r1 followed by r2, i.e. their concatenation.
"One language can be expressed by more than one FA". This statement is ________
Different FAs, e.g. with extra states, can accept the same language.
A regular language:
Every finite language is regular and infinite ones like a* are regular too.
Every regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression. This statement is:
Regular languages are a proper subset of context-free languages.
Consider the language L of strings, defined over Σ = {a,b}, ending in a
Strings ending in a split Σ* into two classes, and by Myhill-Nerode finitely many classes means regular.
The word 'formal' in formal languages means
Formal languages deal with the form (syntax) of strings, not their meaning.
Choose the correct statement.
Moore and Mealy machines only translate input to output; they have no final states and define no language.
If L1 and L2 are expressed by regular expressions r1 and r2, respectively then the language expressed by r1 + r2 will be ________
r1 + r2 is a regular expression, so its language is regular.
The language of all words (made up of a's and b's) with at least two a's can not be described by the regular expression.
Option a forces the word to start with a and have three a's, so it misses words like baa; b and c describe the language.
In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called
A state with no exit is called a dead state, waste basket or Davey John locker.
Choose the incorrect (FALSE) statement.
A Moore machine prints one more character than a Mealy machine for the same input, so c is false.
Choose the incorrect statement:
EQUAL needs unbounded counting, so it is not regular; the other statements are true.
PDA is only used to represent a regular language.
PDAs accept all context-free languages, including nonregular ones.
If L is a regular language then LC is also a regular language.
Regular languages are closed under complement.
A production of the form non-terminal → string of two non-terminal is called a live Production.
In the handouts a live production has the form nonterminal → two nonterminals.
We can find a CFG corresponding to a DFA.
Every FA language is regular and every regular language has a (regular) CFG.
A CFG is said to be ambiguous if there exists at least one word of its language that can be generated by different production trees
This is the definition of an ambiguous CFG.
The production of the form non-terminal → one non-terminal is called unit production
A unit production has one nonterminal on each side.
DFA and PDA are equal in power.
A PDA accepts nonregular context-free languages that no DFA accepts.
A production of the form non-terminal → non-terminal non-terminal is called a dead Production.
A dead production has the form nonterminal → terminal; two nonterminals on the right make a live production.
Two FAs are equivalent if they have same no. of states.
FAs are equivalent when they accept the same language, not when they have the same number of states.
There exist exactly two different derivations in an ambiguous CFG for a word.
Ambiguity needs at least two different trees for some word, not exactly two.
Regular languages are closed under Union, Concatenation and Kleene star.
If r1 and r2 are REs then r1 + r2, r1r2 and r1* are REs too.
PDA is stronger than FA.
PDAs accept every regular language plus nonregular context-free languages.
The reverse of the string sbfsbb over { sb, f, b }
Tokens are sb, f, sb, b; reversed they give b sb f sb = bsbfsb.
Two languages are said to belong to same class if they end in the same state when they run over an FA, that state
Strings are in the same class if they end in the same state, whether or not it is final.
According to Myhill Nerode theorem, if L generates finite no. of classes then L is ________
Myhill-Nerode: finitely many classes means L is regular.
If the intersection of two regular languages is regular then the complement of the intersection of these two languages is also regular
The complement of a regular language is regular.
In pumping lemma theorem (x y^n z) the range of n is
The handout version states that xy^n z is in L for n = 1, 2, 3, ...
The complement of a regular language is also a regular
Regular languages are closed under complement.
For language L defined over {a, b},then L partitions {a, b}* into ________ classes
Myhill-Nerode: L partitions Σ* into distinct classes.
If an FA accept a word then there must exist a path from
Acceptance means the word traces a path from the initial state to a final state.
If an FA already accepts the language expressed by the closure of certain RE, then the given FA is the required FA.
An FA that already accepts r* needs no change to serve as the FA for r*.
If R is a regular language and L is some language, and L U R is a regular language, then L must be a regular language.
If R = Σ*, then L ∪ R = Σ* is regular for any L, even a nonregular one.
FA corresponding to an NFA can be built by introducing an empty state for a letter having
A missing transition in the NFA becomes a move to an empty (dead) state in the FA.
(a* + b*)* = (a + b)* this expression is ________
a* + b* contains a and b, so its closure is all strings.
If S = { x }, then S* will be
The Kleene star always includes the null string Λ.
The states in which there is no way to leave after entry are called
A state with no exit is called a dead state, waste basket or Davey John locker.
If S = {ab, bb}, then S* will not contain
bbba cannot be split into ab and bb blocks; the other three can.
According to theory of automata there are ________ types of languages
The course divides languages into formal and informal languages.
What do automata mean?
Automaton means something that works automatically.
What is false about the term alphabet?
An alphabet is a finite non-empty set of letters.
Formal is also known as ________
Formal languages are also called syntactic languages.
Following are types of languages
The two types of languages are formal and informal.
Consider the following production (of a CFG): S->XYZ Here ________ is left most nonterminal in working string. Note: S, X, Y and Z are all nonterminals
In the working string XYZ the first nonterminal from the left is X.
A PDA consists of the following:
All three are listed parts of a PDA.
The unit and null productions can be deleted from a CFG
Both can be removed while keeping the language (except possibly Λ).
The structure given below is called ________ S -> aA|bB A -> aS|a B -> bS|b
A set of productions with a start symbol is a context-free grammar.
Which of the following states is not part of PDA
A PDA has START, READ, PUSH, POP, ACCEPT and REJECT states but no WRITE state.
The production of the form: nonterminal --> one nonterminal is called the ________
One nonterminal on each side is a unit production.
A ________ is the one for which every input string has a unique path through the machine.
Deterministic means each input string has exactly one path.
The CFG is said to be ambiguous if there exist at least one word of its language that can be generated by the ________ production trees
Ambiguous means some word has more than one production tree.
In a CFG the nonterminal that occurs first from the left in the working string, is said to be ________
The first nonterminal from the left is the leftmost nonterminal.
The unit production is
A unit production replaces one nonterminal by one nonterminal.
A ________ operator adds a new letter at the top of STACK
PUSH puts a letter on top of the stack.
PDA stands for ________
PDA means pushdown automaton.
In a STACK:
A stack is last-in first-out, so the first element pushed is popped last.
Kleene star closure can be defined
Kleene closure can be taken of any set of strings.
While finding RE corresponding to TG, we connect the new start state to the old start state by the transition labeled by
The new start state is joined to old start states by Λ-edges so no input is read.
For a given input, it provides the compliment of Boolean AND output.
NAND outputs NOT of AND.
It delays the transmission of signal along the wire by one step (clock pulse).
A DELAY box holds the signal for one clock pulse.
For the given input, it provides the Boolean OR output
An OR box outputs the Boolean OR.
For the given input, AND box provides the Boolean AND output.
An AND box outputs the Boolean AND of its inputs.
The current in the wire is indicated by 1 and 0 indicates the absence of the current.
In the circuit model, 1 means current and 0 means no current.
If L1 and L2 are regular languages ________ is/are also regular language(s).
Regular languages are closed under union, concatenation and Kleene star.
Let L be a language defined over an alphabet Σ, then the language of strings, defined over Σ, not belonging to L, is called Complement of the language L, denoted by Lc or L'.
This is the definition of the complement of L.
To describe the complement of a language, it is very important to describe the ________ of that language over which the language is defined.
The complement is taken relative to Σ*, so the alphabet must be known.
For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = Lc
(Lc)c equals L, not Lc, so the stated equation is false.
If L is a regular language then, ________ is also a regular language.
The complement Lc of a regular language is regular.
Converting each of the final states of F to non-final states and old non-final states of F to final states, FA thus obtained will reject every string belonging to L and will accept every string, defined over Σ, not belonging to L. is called
Swapping final and non-final states gives the FA for the complement.
If L1 and L2 are two regular languages, then L1 U L2 is not a regular.
The union of regular languages is regular.
If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.
By Kleene's theorem every regular language has an FA.
L= language of words containing even number of a's. Regular Expression is
Each block is b or a pair of a's with b's between, so the total number of a's is even.
Let L be any infinite regular language, defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ* such that all the strings of the form xy^n z for n=1,2,3, ... are the words in L. called.
This statement is the pumping lemma.
Languages are proved to be regular or non regular using pumping lemma.
The pumping lemma can only show a language is nonregular; some nonregular languages also satisfy it.
If, two strings x and y, defined over Σ, are run over an FA accepting the language L, then x and y are said to belong to the same class if they end in the same state, no matter that state is final or not.
Classes are defined by the ending state, final or not.
Myhill Nerode theorem is consisting of the followings,
The theorem has all three parts.
The language Q is said to be quotient of two regular languages P and R, denoted by ________ if PQ=R.
If PQ = R then Q is the quotient R/P.
If two languages R and Q are given, then the prefixes of Q in R denoted by Pref(Q in R).
Pref(Q in R) is the notation for the prefixes of Q in R.
Let Q = {aa, abaaabb, bbaaaaa, bbbbbbbbbb} and R = {b, bbbb, bbbaaa, bbbaaaaa}. Pref (Q in R) is equal to,
bbba·aa, bbbaaa·aa and b·bbaaaaa are in R, giving {b, bbba, bbbaaa}.
If R is regular language and Q is any language (regular/ non regular), then Pref (Q in R) is ________ .
Pref(Q in R) is regular whenever R is regular.
Between the two consecutive joints on a path
In conversion form, each row between joints pops one character and may push any number.
There is a problem in deciding whether a state of FA should be marked or not when the language Q is infinite.
For infinite Q we cannot test every word of Q to decide the marking.
If an effectively solvable problem has answered in yes or no, then this solution is called ________
An algorithm that answers yes or no is a decision procedure.
The following problem(s) ________ is/are called decidable problem(s).
Both equivalence questions have decision procedures.
To examine whether a certain FA accepts any words, it is required to seek the paths from ________ state.
The FA accepts some word exactly when a final state is reachable from the initial state.
The CFG is not said to be ambiguous if there exists atleast one word of its language that can be generated by the different production trees,
Such a CFG is ambiguous, so the statement is false.
Proof(Kleene's Theorem Part II) If a TG has more than one start states, then
A new single start state is added with Λ-edges to the old start states.
Which of the following statement is NOT true about TG?
A TG may have several or no paths for a string, so exactly one is not required.
Kleene's theorem states
Kleene's theorem says FA, TG and RE describe the same (regular) languages.
A language accepted by an FA is also accepted by
By Kleene's theorem the language also has a TG, a GTG and an RE.
Identify FALSE statement:
Some CFGs generate nonregular languages, so not every CFG has an RE.
In large FA with thousands of states and millions of directed edges, without an effective procedure it is ________ to find a path from initial to final state.
The handout says that without an algorithm such a path is impossible to find by inspection.
If there is no final state of two FAs then their ________ also have no ________ state
A union state is final only if a component is final, so with no final states the union has none.
In the context of Myhill Nerode theorem, for even-even language sigma star can be partitioned into ________ number of classes.
EVEN-EVEN's FA has four states (parities of a's and b's), giving four classes.
The product of two regular languages is ________.
Regular languages are closed under concatenation.
A problem that has decision procedure is called ________ problem.
A problem with a decision procedure is decidable.
For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is ________.
All strings of lengths N to 2N-1 are tested, and there are m^k strings of length k.
If (L1 ∩ L2c) ∪ (L1c ∩ L2) is regular language that accepts the words which are in L1 but not in L2 or else in L2 but not in L1. The corresponding FA cannot accept any word which is in ________ L1 and L2.
This symmetric difference excludes words that are in both L1 and L2.
Incase of Myhill Nerode theorem, if a language L partitions sigma star into distinct classes and L is also regular then L generates ________ number of classes.
Myhill-Nerode: a regular language generates finitely many classes.
The production of the form nonterminal → one nonterminal is called the :
Non-terminal → one non-terminal is a unit production.
Let Q and R be expressed by ab*a and (ba)* respectively i.e Q={aa ,aba ,abba ……}and R={Λ,ba, baba,bababa…….}. aba is the only word in Q which can make a word in R, because the words in R don't contain the
Words of R alternate b and a, so they never contain a double letter such as aa or bb.
Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :
Strings not in L form its complement.
For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = L
Complementing twice gives L back.
consider a language L defined over an alphabet ∑ if two strings x and y defined over ∑ are run over an FA accepting the language L,then x and y are said to belong to the same ………. if they end in the same …….
Strings ending in the same state belong to the same class.
The regular expression defining the language L1 U L2 can be obtained, converting and reducing the previous ------------- into a ------------ as after eliminating states.
The FA is turned into a GTG and states are eliminated to get the RE.
The regular expression thus obtained if contains at least one word then the language is not empty otherwise the language is :
If the RE defines no word, the language is empty.
it is very important to determine which sequences of rows do correspond to possible paths through the:
Only some row sequences of the summary table are real paths through the PDA.
Before the CFG corresponding to the given PDA is determined,the PDA is converted in to the standard form which is called the:
A PDA is first put into conversion form.
……………… is a place where the input letters can be placed until these letters are referred again. It can store as many letters as one can in a long column .
The handout defines the PUSHDOWN STACK this way.
Which of the following statement is NOT true:
Every FA is an NFA and every NFA is a TG, but a TG (with string labels) is not in general an NFA.
Let FA3 be an FA accepting L1∩L2 then the initial state of FA3 must be correspond to the initial state of………. and initial state of ………
The intersection machine starts at the pair of initial states of FA1 and FA2.
FA corresponding to an NFA can be built by introducing a state corresponding to the combination of states, for a letter having
Several transitions on one letter are merged into one combined state.
A DFA with n states must accept at least one string of length greater than n.
A DFA may accept a finite language or no word at all.
For every three regular expressions R, S, and T, the languages denoted by R(S U T) and (RS) U (RT) are the same.
Concatenation distributes over union.
Choose the right option: (A) In a Mealy machine, the set of letters and the set of output characters must be same. (B) In a Mealy machine, the set of letters and the set of output characters may not be same.
Input letters and output characters of a Mealy machine can be different sets.
The following problem(s) ------------- is/are called decidable problem(s). The two regular expressions define the:
Both equivalence questions are decidable.
If F accept an ………….. language then there are some words w s.t N ≤ length (w) < 2N :
An FA with N states accepts an infinite language iff it accepts a word with N ≤ length < 2N.
The values of input (say a & b) does not remain same in one cycle due to
Input values change at each clock pulse.
The reverse of the string sbfsbb over { sb, f, b}
sb·f·sb·b reversed is b·sb·f·sb.
If L1 and L2 are regular languages then which statement is NOT true?
Quotient, union and concatenation of regular languages are all regular.
the moment a final state of ……….. FA is entered ,the possibility of the initial state of ……….. FA will be included as well:
In the concatenation FA, reaching a final state of the first FA adds the initial state of the second.
An FA has same initial and final state, then it means that it has no final state.
A state can be both initial and final; the FA then accepts Λ.
If L1 and L2 are two regular languages then L1∩L2 is also :
Regular languages are closed under intersection.
For language L defined over {a, b},then L partitions {a, b}* into …… classes:
L partitions Σ* into distinct classes.
If an effectively solvable problem has answer in yes or no ,then this solution is called :
A yes/no algorithm is a decision procedure.
If r1 = (aa + bb) and r2 = ( a + b) then the language (a + b)* (aa + bb)* will be generated by :
(a+b)* is (r2)* and (aa+bb)* is (r1)*.
In FA starting state is represented by a sign.
The start state is marked with a minus sign and final states with plus.
The production of the form nonterminal →string of two nonterminals is called a:
Non-terminal → two non-terminals is a live production.
Converting the given CFG in CNF is the first rule of
The CYK membership algorithm first puts the CFG in CNF.
If a language can be expressed by a regular expression, then its complement cannot be expressed by a regular expression. This statement is:
The complement of a regular language is regular, so it has an RE too.
Which statement is true?
Words are those strings that belong to a language, so every word is a string but not every string is a word.
If L1 and L2 are expressed by r1 and r2, respectively then the language expressed by (r1)(r2) will be ________
The concatenation of two regular expressions is again a regular expression, so its language is regular.
If an FA accepts no string, then language is denoted by ________
The empty language can be written either as {} or as Ø.
Which of the following pairs of regular expressions are not equivalent?
a*b* contains aab while (ab)* does not, so they are not equivalent.
Which of the following statement is correct?
A Moore machine prints a character in its start state before reading input, so its output is one longer than the input.
Which one of the following statements is INCORRECT:
EQUAL (equal a's and b's) is nonregular, so calling it regular is incorrect.
Σ = {a,b} then string abbabb has length equal to ________.
abbabb has six letters, so its length is 6.
If r1 and r2 are regular expressions then (r1)(r2) is a ________.
By the recursive definition of regular expressions, the concatenation of two REs is again an RE.
Which of the following is RE for a language defined over Σ={a,b} having words starting with a:
a(a+b)* puts an a first and allows any string after it.
The ______ machine helps in building a machine that can perform the addition of binary numbers.
The incrementing (Mealy) machine adds 1 to a binary number and is the basis for a binary adder.
A regular language ________.
Every finite language is regular and many infinite languages (such as a*) are regular too.
If a language can be expressed by a regular expression, then its complement is ________.
Regular languages are closed under complement: swap final and non-final states of its FA.
If a given Context Free grammar (CFG) contains a production of the form S→Λ, then ________
S→Λ lets the grammar generate the null string, so the language has at least one word.
We can have more than one parse trees for a given string in case of ________ Context Free Grammar (CFG).
A CFG is ambiguous when some word has more than one derivation (parse) tree.
The language of aⁿbⁿ can be expressed by:
aⁿbⁿ is nonregular, so no FA, TG or GTG accepts it, but it is context free and a PDA accepts it.
Which of the following theorem partitions Σ* into distinct classes?
The Myhill-Nerode theorem divides Σ* into classes of indistinguishable strings.
The languages are supposed to be ________ in case of testing pumping lemma.
The pumping lemma proof starts by assuming the language is regular and then reaches a contradiction.
Which of the following states do not have outgoing edges:
ACCEPT is a halting state, so no edge leaves it.
"One GTG can generate ________ language".
A GTG, like any machine, defines exactly one language: the set of words it accepts.
Regular languages are closed under ________
If L1 and L2 are regular then L1 + L2 and L1L2 are regular too.
Σ = {a, Aa, Abb}, then string aAaAbbAa has length equal to ________.
aAaAbbAa splits uniquely into the letters a, Aa, Abb, Aa, so its length is 4.
In ________ there must be transition for all letters.
In an FA every state must have exactly one outgoing transition for each letter of Σ.
Consider the following Context Free Grammar (CFG) and select the correct choice S → AB A → BSB | a | b B → CC C → SS | b | bb
S ⇒ AB ⇒ aB ⇒ aCC ⇒ abC ⇒ abb, so abb is generated; every word has length at least 3, so b is not.
Language of strings having even number of a's is considered to be:
An FA with two states (even/odd count of a's) accepts it, so it is regular.
Which of the following refers to an effectively solvable problem having answer in "Yes" or "No"?
An effective procedure that always answers a yes/no question is called a decision procedure.
Concatenation of r1 and r2 will be shown as:
Concatenation of r1 followed by r2 is written r1r2; + denotes union.
The language of a^n b^n can be expressed by:
a^n b^n is nonregular but context free, so it needs a PDA's stack to count a's.
No MCQs match this filter.Is filter mein koi MCQ nahi.
What is the difference between the strings and the words of a language?
A string is any finite sequence of letters of an alphabet. The words of a language are only those strings that satisfy the rule defining that language. Example: over {a,b}, ab and bbb are both strings, but in the language of strings with no a's and an odd number of b's only b, bbb, bbbbb, ... are words. So every word is a string, but not every string is a word.
What is the difference between an Alphabet and an element of a set. Whether Alphabet is an element of a set or it is a set itself?
An alphabet is itself a set: a finite non-empty set of symbols. Its elements are called letters. Example: the binary alphabet Σ = {0,1} is a set whose elements (letters) are 0 and 1, just as 1, 2, 3 are elements of the set of natural numbers.
What is Null String (Λ)?
The null (empty) string is the string with no letters at all, i.e. of length 0. It is written Λ (or λ). Concatenating it with any string leaves that string unchanged: Λw = wΛ = w.
What is PALINDROME?
PALINDROME is the language over an alphabet Σ consisting of Λ and all strings s with Rev(s) = s, i.e. strings that read the same forwards and backwards. Over {a,b}: Λ, a, b, aa, bb, aba, bab, aabaa, ... Its words are called palindromes.
What is the concept of valid and invalid alphabets?
An alphabet whose letters may be several symbols long is valid only if no letter is a prefix (starting part) of another letter, so that every string can be split into letters in only one way. Example: {a, b, cd} is valid; {a, b, ac} is invalid because a is the start of ac, so a string like ac cannot be tokenized uniquely. A letter may end with another letter (be a suffix of it).
What is ALGOL?
ALGOL (ALGOrithmic Language) is a high-level programming language family (ALGOL 58, ALGOL 60, ALGOL 68) designed by an international committee from the late 1950s for scientific computation. It introduced block structure and nested scopes, its syntax was the first to be formally specified with a grammar (BNF), and it strongly influenced later languages.
What is Non-Determinism and Determinism and what is the difference between them?
In a deterministic machine the current state and current input letter fix exactly one next move. In a nondeterministic machine there may be zero, one or several possible moves for a state and letter (and possibly Λ-moves); a string is accepted if at least one possible path leads to acceptance. For finite automata both have the same power: every NFA can be converted to an equivalent deterministic FA.
What is meant by equivalent FA's?
Two FAs are equivalent if they accept exactly the same language, i.e. every string accepted by one is accepted by the other and vice versa, even if their states and transitions differ.
What is the difference between Palindrome and Reverse function?
Reverse is an operation on a single string: Rev(s) writes the letters of s in the opposite order, e.g. Rev(623) = 326, Rev(abb) = bba. PALINDROME is a language: the set of Λ and all strings s with Rev(s) = s, e.g. {Λ, a, b, aa, bb, aba, bab, ...}. So reverse is a function used to define the palindrome language.
Define Kleene Star?
For an alphabet (or any set of strings) Σ, the Kleene star closure Σ* is the set of all strings formed by concatenating zero or more elements of Σ, including Λ. Examples: if Σ = {x}, Σ* = {Λ, x, xx, xxx, ...}; if Σ = {0,1}, Σ* = {Λ, 0, 1, 00, 01, 10, 11, ...}. For a non-empty set containing a non-null string, the closure is an infinite language.
Valid/In-Valid alphabets?
An alphabet is valid if no letter of it is the beginning (prefix) of another letter, so strings can be tokenized uniquely; otherwise it is invalid. Example: {B, aB, bab, d} is valid, {B, Ba, bab, d} is invalid because B is the start of Ba.
What is Reverse of a string?
The reverse of a string s, Rev(s), is the string formed by writing the letters of s in the opposite order, treating each letter of the alphabet as one unit (letters themselves are not reversed). Example: over {a,b}, Rev(abbaa) = aabba; over Σ = {B, aB, bab, d}, Rev(BaBbabBd) = dBbabaBB. The alphabet is unchanged.
Differentiate Kleene Star Closure and PLUS?
Kleene star Σ* is the set of all concatenations of zero or more elements of Σ, so it always contains Λ. PLUS Σ+ is the set of concatenations of one or more elements, so it contains Λ only if Λ is already in Σ. Example: for Σ = {a}, a* = {Λ, a, aa, ...} and a+ = {a, aa, aaa, ...}; Σ+ = ΣΣ*.
Define Regular Expression?
A regular expression is a formula that defines a language, built recursively: (1) every letter of Σ and Λ are regular expressions; (2) if r1 and r2 are regular expressions then so are (r1), r1r2 (concatenation), r1 + r2 (union) and r1* (closure); (3) nothing else is a regular expression. Example: a* defines {Λ, a, aa, ...} and a+ defines {a, aa, ...}.
What is the concept of FA also known as FSM (Finite State Machine)?
A finite automaton (finite state machine) is an abstract machine with a finite number of states, one initial state, some final states, an input alphabet and a transition for each state and each letter. It reads the input one letter at a time and changes state; it has no memory other than its current state. It accepts a string if it ends in a final state, and the languages it recognizes are exactly the regular languages.
What is the difference between FA, TG, GTG?
FA: exactly one start state, and from every state exactly one transition for every letter; edges are labeled with single letters; no Λ-edges. TG: one or more start states; edges may be labeled with strings (words) or Λ; a state need not have an edge for every letter and may have several for the same letter. GTG: like a TG but edges are labeled with regular expressions. Every FA is a TG and every TG is a GTG, but not conversely; all three accept exactly the regular languages.
What is the difference between FA's and TG's. Why we need TG's when we have FA's?
A TG is a generalization of an FA: it may have more than one start state, edges labeled with strings or Λ (moving without reading input), missing edges for some letters and several edges for the same letter. An FA must have one start state and exactly one single-letter edge per letter from each state. TGs are needed because they are often much easier to design for a language and are used in proving Kleene's theorem; by Kleene's theorem a TG can always be converted to an equivalent FA, so they have the same power.
What is the concept of the Union of FA's?
The union of FA1 and FA2 is an FA that accepts every string accepted by FA1 or by FA2 (or both), i.e. the language L1 ∪ L2 (corresponding to RE r1 + r2). It is built by taking states as pairs (state of FA1, state of FA2), starting from the pair of the two initial states, following both machines on each letter, and making a pair final if either component is final.
What is the difference between TG and GTG?
In a TG the edges are labeled with letters, strings or Λ; in a GTG the edges are labeled with regular expressions, so one edge can represent a whole set of strings. Every TG is a GTG.
How one can create RE of a particular language?
There is no fixed algorithm; it comes from understanding the language and practice. Useful steps: list the shortest words and look for the pattern; a finite language can be written as the sum of its words (e.g. aaa + aab + ...); use * for parts that repeat; remember whether Λ belongs to the language. Examples: all strings starting with a: a(a+b)*; ending with b: (a+b)*b; even length: ((a+b)(a+b))*. Check that the RE generates all words of the language and nothing else.
What is the diagrammatically difference between FA's and TG's?
In an FA diagram there is exactly one start state, every state has exactly one outgoing edge for each letter of Σ, and each edge is labeled with a single letter. In a TG diagram there may be several start states, some states may have no edge (or several edges) for a letter, and edges may be labeled with strings of letters or with Λ.
What is the corresponding FA for RE = aa((a+b)(a+b))*
The language is aa followed by an even-length string, i.e. strings starting with aa and having even length. FA over {a,b}: start state q0; q0 -a-> q1, q0 -b-> D; q1 -a-> q2, q1 -b-> D; q2 (final) -a,b-> q3; q3 -a,b-> q2; D is a dead state with a,b loops. Only q2 is final.
What is difference between FA's and NFA's. Are they opposite to each other?
In an FA each state has exactly one transition for each letter. In an NFA a state may have several transitions for the same letter or none for some letter, so there may be choices; a string is accepted if some path ends in a final state. They are not opposites: every FA is a special case of an NFA, and every NFA can be converted to an equivalent FA, so they accept the same class of languages.
Differentiate between (a,b) and (a+b)?
(a+b) is a regular expression meaning one choice of either a or b; its language is {a, b}. (a, b) is not regular-expression notation; the comma is only used to list elements, as in the alphabet Σ = {a, b}. Both refer to the same two letters, but in an RE the choice must be written with +.
What is the difference between how's FA and TG. Why we need TG's when we have FA's?
A TG generalizes an FA: it may have several start states, Λ-edges, string labels and missing or repeated edges for a letter, while an FA has one start state and exactly one single-letter edge per letter from each state. TGs are easier to design and are used in Kleene's theorem; every TG can be converted to an equivalent FA.
What is the difference between GT and GTG?
In a TG edges are labeled with letters, strings or Λ; in a GTG edges are labeled with regular expressions.
How to create a RE of a particular Language?
Study the words of the language, starting with the shortest, and find a pattern; use + for choices, concatenation for sequence and * for repetition; include Λ when the language contains it. Then check that the RE generates every word of the language and no other string.
How diagrams of FA's are created?
There is no fixed formula. Decide what each state must remember about the input read so far (e.g. last letter, parity, a found substring), create one state for each such situation, mark the initial state and the final states, and draw from every state one edge for each letter. Then test the FA with words that should be accepted and rejected.
What is the difference between FA's, and TG's?
FA: exactly one initial state, edges labeled with single letters, exactly one edge for each letter from every state. TG: may have more than one initial state, edges may be labeled with strings or Λ, and a state may have no edge or several edges for a letter.
What is the exact definition of FA?
A finite automaton is a collection of: (1) a finite number of states, one of which is initial and some (possibly none) final; (2) a finite alphabet Σ of input letters; (3) a finite set of transitions telling, for each state and each letter, the state to move to.
For RE = aa((a+b)(a+b))* what will be its corresponding FA?
Start q0; q0 -a-> q1, q0 -b-> D; q1 -a-> q2, q1 -b-> D; q2 final; q2 -a,b-> q3; q3 -a,b-> q2; dead state D loops on a,b. It accepts strings starting with aa of even length.
What is the difference between FA and NFA?
An FA has exactly one transition for each letter from each state; an NFA may have several or none. Every FA is an NFA, and every NFA can be converted to an equivalent FA.
What is the method to understanding FA's and NFA's
To run a string on an FA, start at the initial state and follow, letter by letter, the unique edge for each letter; the string is accepted if the last state is final. In an NFA there may be several edges or none for a letter, so consider all possible paths; the string is accepted if at least one path ends in a final state after reading the whole string. The FA describes a language when it accepts all words of the language and rejects all other strings.
What is the concept of Nondeterministic Finite Automaton (NFA)?
An NFA is a finite automaton in which the current state and input letter do not uniquely determine the next state: from a state there may be several edges with the same letter or no edge for a letter. It has finite states, an alphabet, transitions, one initial state and final states. A string is accepted if some path reading it ends in a final state. NFAs accept exactly the regular languages and can be converted to FAs.
If a language can be expressed in the form of FA than why it is needed to use NFA?
An NFA has fewer restrictions, so for many languages it is much easier and smaller to design. It is also convenient in proofs (e.g. building machines for union, concatenation and closure). Since every NFA can be converted to an equivalent FA, one can design an NFA first and then convert it.
How to made NFA corresponding to the closure of an FA?
Λ must be accepted, but simply making the old initial state final may accept extra strings. Instead, add a new state that is both initial and final, give it the same outgoing edges as the old initial state, and from every final state add edges (copies of the old initial state's outgoing edges) so that after a word the machine can start the next word. The result is an NFA for the closure L*.
What is the difference between Union of two FA's, Concatenation of two FA's and closure of two FA's?
Union FA1 ∪ FA2 accepts strings accepted by FA1 or by FA2 (RE r1 + r2). Concatenation FA1FA2 accepts strings that can be split into a first part accepted by FA1 followed by a second part accepted by FA2 (RE r1r2). Closure FA1* accepts Λ and all concatenations of one or more words of FA1 (RE r1*). Example: if FA1 accepts strings ending in a and FA2 strings ending in b, the union accepts strings ending in a or b, the concatenation accepts strings such as ab, abab, and FA1* accepts Λ and all strings ending in a.
How Moore and Mealy machine works in Computer Memory what is their importance in Computing?
Moore and Mealy machines are finite automata with output: they read an input string and produce an output string (Moore prints at states, Mealy along edges). They model sequential circuits and computations such as an incrementing machine, a 1's complement machine or a binary adder, where the state stores the needed information (like a carry). So they are the theoretical model of circuits with memory in computers.
What is sequential circuit?
A sequential circuit is a digital circuit whose output depends on the present inputs and on its present state, which is held in memory elements such as flip-flops. With n flip-flops up to 2^n states can be represented. Its next state and output are functions of the present input and present state, which is why it can be modeled by a Mealy or Moore machine.
What is the concept of Pumping Lemma I and II and what is the difference between pumping Lemma 1 and pumping Lemma 2?
Both are used to prove that a language is nonregular. Version I: if L is an infinite regular language, then there are strings x, y, z with y ≠ Λ such that xy^n z is in L for all n ≥ 1. Version II adds the condition length(x) + length(y) ≤ N, where N is the number of states of the FA accepting L, for every word w in L with length(w) > N. The extra condition makes version II stronger: some languages such as PALINDROME cannot be shown nonregular with version I (pumping the middle of a palindrome gives palindromes) but can be with version II.
What is the significance of Pumping Lemma II?
Some nonregular languages, such as PALINDROME, have words that can be pumped and remain in the language, so version I cannot prove them nonregular. Version II forces the pumped part y to lie within the first N letters (length(x) + length(y) ≤ N), so a suitable long word can be chosen whose pumping takes it outside the language, proving the language nonregular.
Moore and Mealy machine?
A Moore machine has an output character attached to each state and prints it whenever it enters that state (including the start state, so the output is one character longer than the input). A Mealy machine has the output character on each transition edge and prints it when the edge is used, so the output has the same length as the input. Neither has final states; to run a string, start at the initial state, follow the transitions letter by letter and record the outputs.
What is the difference between semiword and word please also give an example regarding this?
A word is a string of terminals only (Λ included), e.g. abba. A semiword is a string of zero or more terminals followed by exactly one nonterminal at the right end, e.g. aaB, abbA, or just A.
What is the difference between derivation tree and total tree?
A derivation (parse) tree shows how one particular word is generated from the start symbol by a CFG. A total language tree starts from the start symbol and shows all possible derivations, so its leaves include all words of the language generated by the CFG.
What does mean the LANGUAGE IS CLOSED?
A language (or a class of languages) is closed under an operation if applying the operation to its members always gives a member of the same language (class). Example: integers are closed under addition; the language a* is closed under concatenation; regular languages are closed under union, concatenation, Kleene star, complement and intersection.
What are the Productions?
Productions are the grammatical rules of a CFG, of the form nonterminal → finite string of terminals and/or nonterminals. A derivation applies productions, replacing nonterminals step by step, until only terminals remain; the result is a word of the language.
What is the difference between concatenation and intersection of two FA's also what is the difference among Union of two FA's and addition of them?
Intersection of two FAs accepts only strings accepted by both FAs. Concatenation accepts strings that can be split into a first part accepted by FA1 followed by a second part accepted by FA2. Union and addition are the same thing: FA1 + FA2 (FA1 ∪ FA2) accepts strings accepted by at least one of them.
What is the Difference between Nullable and Null production? How to make eliminate Nullable and for Null Productions from the CFG?
A null production has the form N → Λ. A nonterminal is nullable if Λ can be derived from it (directly or through a chain, e.g. W → Z, Z → AB, A → Λ, B → Λ). To eliminate null productions: delete each N → Λ, and for every production containing nullable nonterminals add new productions with every combination of those nullable occurrences removed (never adding X → Λ). Example: X → aNbNa with N → Λ becomes X → aNbNa | abNa | aNba | aba. The new CFG generates the same language except Λ.
Is it possible to make CFG for infix and postfix expression's using derivation tree?
Yes. A CFG can be written for arithmetic expressions in infix, prefix or postfix form (e.g. S → S+S | S*S | number for infix). A derivation tree of an expression shows its structure, and reading the tree in different orders gives the prefix (Polish), infix or postfix form; the tree itself is not used to build the grammar.
What is the uses of push down automata in computing?
A PDA is an FA with a stack as memory, so it recognizes context-free languages such as a^n b^n and balanced parentheses, which FAs cannot. It is the theoretical model of syntax analysis (parsers) in compilers, used to check nested structures in programming languages and expressions.
What is difference between PUSH DOWN STACK and PUSH DOWN STORE?
There is no difference; both names refer to the same last-in-first-out memory attached to a PDA, where letters are pushed on top and popped from the top.
How we can distinguish between CFG and CNF in the questions?
A CFG is in Chomsky Normal Form only if every production is of the form nonterminal → two nonterminals or nonterminal → one terminal. If any production has another form (e.g. mixed terminals and nonterminals, more than two nonterminals, unit or null productions), the CFG is not in CNF.
What is meant by the terms stack consistence and input tape consistence?
Stack consistent: when a path of a PDA is followed, each POP must find on top of the stack exactly the character its edge requires, i.e. a row can pop only what is actually on top of the STACK. Tape consistent: the letters read along the path must be the letters of the input word in order, one at a time from the front of the TAPE.
What is the concept of unit production?
A unit production has the form nonterminal → one nonterminal, e.g. S → A. It can be removed: if S → A and A → a | b, replace it by S → a | b, i.e. give S all the non-unit right-hand sides that A can produce. Unit productions are removed when converting a CFG to CNF.
Why Context Free Grammars are called Context Free?
Because every production has a single nonterminal on its left side, so that nonterminal can be replaced by its right side wherever it appears, regardless of the symbols around it (its context). In context-sensitive grammars a replacement may depend on the neighbouring symbols.
What is Unit Production?
A production in which one nonterminal produces exactly one nonterminal, e.g. A → B.
Give a example of converting a CFG to CNF?
CFG: S → ABC, A → aa | b, B → c, C → d. Replace the terminal a in A → aa by a new nonterminal E → a, and break S → ABC into two-nonterminal productions with D → AB. CNF: S → DC, D → AB, A → EE | b, E → a, B → c, C → d.
How to differentiate between wanted and unwanted branch?
In top-down parsing, starting from the start symbol, wanted branches are the branches of the derivation tree that can lead to the required word; unwanted branches cannot lead to it and are discarded. Example: S → AA, A → a | b; to derive aa the branches using A → b are unwanted.
What is the difference between intersection and union of a language?
The union L1 ∪ L2 contains every word that is in at least one of the languages; the intersection L1 ∩ L2 contains only the words that are in both languages.
What is the difference between Context free languages and regular languages?
Regular languages can be recognized by FAs (no memory besides the state) and described by regular expressions. Context-free languages are generated by CFGs and recognized by PDAs, which have a stack; they include languages like a^n b^n and PALINDROME that need memory and are not regular. Every regular language is context-free, but not every context-free language is regular.
What is the difference between Moore and Mealey machines?
In a Moore machine the output is attached to states and printed on entering a state, starting with the initial state, so the output string is one character longer than the input. In a Mealy machine the output is attached to transitions and printed while moving along an edge, so the output has the same length as the input.
Is Automata Theory is a Programming Subject or theoretical?
It is a theoretical subject. Automata theory studies abstract machines (FA, PDA, Turing machine), the languages they recognize and what can be computed. Its results are applied in practice, for example in compilers, lexical analyzers, parsers and text searching, but the subject itself is mathematical, not programming.
What are practical Examples of the implications of Automata Theory and the formal Languages?
Compilers and interpreters (lexical analysis with FAs, parsing with CFGs and PDAs), text editors and search tools using regular expressions, protocol and hardware design using finite state machines and sequential circuits, and system verification.
What are the Types of Automata?
Main types with the languages they accept: finite automata (regular languages), pushdown automata (context-free languages), linear-bounded automata (context-sensitive languages) and Turing machines (recursively enumerable languages). Other models include random access machines and arrays of automata.
How types of Automata Differ?
They differ in their memory and power: in their complexity, the functions they can compute and the classes of languages they can accept. FAs have no extra memory, PDAs have a stack, and Turing machines have an unbounded read/write tape.
What is the difference between the alphabet and an element of a set?
An alphabet is itself a set (of letters); an element is one member of a set. The letters are the elements of the alphabet, while a set of strings can have elements longer than one letter.
Difference between Palindrome and Reverse function?
Reverse writes a string backwards, e.g. Rev(140) = 041. PALINDROME is the language of Λ and all strings s with Rev(s) = s.
Define Strings?
A string is a concatenation of a finite number of letters from an alphabet. Example: over Σ = {a,b}, a, ab, abba and bbb are strings; Λ is the string with no letters.
Define empty or null strings?
The empty (null) string is the string with no letters, of length 0, written Λ or λ.
Difference between string and word?
A string is any finite sequence of letters of the alphabet; a word is a string that belongs to the language, i.e. satisfies its defining rule.
There are as many palindromes of length 2n as there are of length 2n-1, please explain?
A palindrome of length 2n is completely determined by its first n letters (the rest is their mirror image). A palindrome of length 2n-1 is also determined by its first n letters (the n-th letter is the middle one). Over {a,b} there are 2^n choices in both cases, so the two numbers are equal. Example n = 2: length 4 gives aaaa, abba, baab, bbbb; length 3 gives aaa, aba, bab, bbb.
Why do not we can write ba in the set of PALINDROME while it is reverse of ab.
A string belongs to PALINDROME only if it equals its own reverse. Rev(ba) = ab, which is different from ba, so ba (and ab) are not palindromes. Of the length-2 strings only aa and bb are palindromes.
What are the steps of Recursive Definition of Languages?
Three steps: (1) specify some basic words that are in the language; (2) give rules for constructing more words from words already known to be in the language; (3) declare that no other strings are in the language. Example for EVEN: 2 is in EVEN; if x is in EVEN so is x + 2; nothing else is in EVEN.
Strings that ending in a and strings containing exactly one a.
Over {a,b}: strings ending in a are given by (a+b)*a, e.g. a, aa, ba, aba, bba. Strings containing exactly one a are given by b*ab*, e.g. a, ab, ba, bab, abb, bba.
What is Lexical Analyzer?
The lexical analyzer (scanner) is the first phase of a compiler. It reads the source characters and groups them into tokens such as identifiers, constants, operators, keywords and punctuation, usually by using finite automata/regular expressions, and passes the tokens (with attributes stored in the symbol table) to the parser.
What is accepting string language?
A string is accepted by a machine if processing it leads to acceptance (for an FA, ending in a final state; for a PDA or TM, reaching ACCEPT/HALT). The language accepted by the machine is the set of all strings it accepts; strings not accepted are rejected.
What is transition table?
A transition table is a tabular representation of an FA's transitions: rows correspond to states, columns to input letters, and each entry gives the next state. The initial state and the final states are marked (e.g. with - and +, or an arrow and a star).
What does it means by the transition?
A transition is a move of the machine from one state to another on reading an input letter (or string in a TG). In an FA every state must have exactly one transition for each letter of the alphabet.
What is Null?
Null (Λ) is the string with no letters, of length 0. For any string or language: ΛS = SΛ = S. If Σ is empty, Σ* = {Λ}; also {Λ}* = {Λ} because ΛΛ = Λ.
What is the difference between Regular Languages and Non Regular Languages?
A regular language can be expressed by a regular expression (equivalently accepted by an FA or TG). A nonregular language cannot be expressed by any regular expression or accepted by any FA, e.g. {a^n b^n : n ≥ 0} and PALINDROME.
What is NFA?
An NFA is a finite automaton in which a state may have several or no transitions for a letter; it accepts a string if some path ends in a final state. It accepts exactly the regular languages.
What is a main difference between NFA and FA?
In an FA each state has exactly one transition per letter (no choices); in an NFA a state may have several or no transitions for a letter, and a string is accepted if some path reaches a final state.
How to obtain 9's complement?
The 9's complement of a decimal number is obtained by subtracting each digit from 9 (equivalently, (10^n - 1) - N for an n-digit integer N). Example: the 9's complement of 52520 is 99999 - 52520 = 47479.
What is DELAY box?
A DELAY box (as used with sequential circuits modeled by Mealy machines) is a memory element, like a flip-flop, that holds its input for one time step and outputs it at the next step. It stores the state of the circuit.
What is the difference between pumping Lemma 1 and pumping Lemma 2?
Both prove languages nonregular. Version II adds the condition length(x) + length(y) ≤ N (number of states), which lets it prove languages such as PALINDROME nonregular where version I fails.
What is pumping lemma? And what is history?
The pumping lemma for regular languages: if L is an infinite regular language accepted by an FA with N states, then every word w in L longer than N can be written w = xyz with y ≠ Λ (and, in version II, length(x) + length(y) ≤ N) such that xy^n z is in L for all n. It holds because any path longer than N must repeat a state, forming a loop that can be repeated. It is used to prove that a language is not regular. It was first stated by Bar-Hillel, Perles and Shamir (1961).
What is the difference between semi word and word?
A word is a string of terminals only; a semiword is a string of terminals (possibly none) followed by exactly one nonterminal on the right, e.g. aabA.
How to identify a production by it, ambiguity will be removed?
First find a word that has two different derivation trees and see which productions allow the choice. Then rewrite the grammar so that only one structure is possible, for example by adding parentheses or new nonterminals that fix precedence and associativity. Example: S → S+S | S*S | number is ambiguous; the PLUS-TIMES grammar S → E, E → T+E | T, T → F*T | F, F → (E) | i removes the ambiguity by making * bind tighter than +.
Difference between Nullable and Null production? How to make CFG for Nullable and for Null?
A null production is N → Λ; a nullable nonterminal is one from which Λ can be derived. Eliminate null productions by deleting them and adding, for each production with nullable nonterminals, versions with those nonterminals removed (e.g. X → aNbNa gives also abNa, aNba, aba).
What are the uses of push down automata in computing?
PDAs recognize context-free languages and model parsers used in compilers to check nested syntax such as balanced parentheses and expressions.
How to accommodate NULL string if it is part of language during converting from CFG to CNF and building FA's?
A CFG in CNF cannot generate Λ, so the CNF grammar generates L - {Λ}; if Λ must be included it has to be handled separately (e.g. by allowing S → Λ as a special case). In an FA, Λ is accepted by making the initial state also a final state; nothing else changes.
How to accommodate NULL string if it is part of language during converting from CFG to CNF and in building PDA?
The CNF grammar generates L - {Λ}, so Λ must be handled separately. A PDA accepts Λ if there is a path from START that reads the blank Δ at once and reaches ACCEPT; when the PDA is built from the CFG, Λ is accepted when S can produce Λ.
What is Push down Automata?
A pushdown automaton consists of: an input alphabet Σ; an input TAPE with the input string followed by blanks; a stack alphabet Γ; a pushdown STACK, initially empty (blanks); one START state; halt states ACCEPT and REJECT; PUSH states that put a character on top of the STACK; POP states that remove the top character and branch on it; and READ states that read the next input letter and branch on it. PDAs accept context-free languages.
Why we study Automata?
Automata theory studies abstract machines and the languages they recognize, telling us what can and cannot be computed and with what resources. It covers finite automata and regular languages, context-free grammars and PDAs, Turing machines and decidability. Its ideas are used in compilers, programming languages, text processing and hardware design, and it develops precise, formal reasoning.
What is valid and invalid alphabets explain with example?
An alphabet is valid if no letter is the start of another letter. Σ1 = {B, aB, bab, d} is valid, so a string like BaBbabBd splits uniquely into B, aB, bab, B, d. Σ2 = {B, Ba, bab, d} is invalid because B is the start of Ba, so it is unclear how to tokenize a string containing Ba.
Why we use Capital Letters for Languages. Is it possible to combine two languages together like EVEN-EVEN & EQUAL, and so on?
Capital letters are only a naming convention to distinguish languages (sets) from strings and letters. Yes, languages can be combined with set operations such as union, intersection and concatenation; e.g. EVEN-EVEN ∩ EQUAL is the language of strings with equal and even numbers of a's and b's.
What are the rules to form WORDS in languages developed by Automata? Are strings not following any rule?
Each language has its own defining rule; the strings satisfying it are the words. Example: for the language of even-length strings over {a,b}, aa, abba are words but a, aba are not. Strings in general are any finite sequences of letters and need not follow a rule; only words of a particular language must.
What are graphs of palindromes of length 2n and length 2n-1?
Even-length palindromes are symmetric about the middle line and odd-length palindromes about the middle letter. Each is determined by its first n letters, so over {a,b} both lengths have 2^n palindromes; e.g. length 4: aaaa, abba, baab, bbbb and length 3: aaa, aba, bab, bbb.
How can we write a RE for a given number of words?
For a finite language, join all its words with +; e.g. all strings of length exactly three over {a,b}: aaa + aab + aba + abb + baa + bab + bba + bbb, which can be written (a+b)(a+b)(a+b) = (a+b)^3. Similarly all seven-letter strings: (a+b)^7, and all strings of any length: (a+b)*.
Please explain that in some expression having more then one plus sign the resulting string is only one from them or it can be more then one? For example if there is an expression: a + b + c, with out any small bracket between them the resultant string is a or b or c OR it can be both a or b and c, a and b or c
a + b + c means a single choice among the alternatives: it generates exactly one of a, b or c each time (the language {a, b, c}); + between terms always means choose one of them.
One Language generates many REs?
Yes. A language can be described by many different regular expressions; such REs are called equivalent. Example: (a+b)*(aa+bb) and (a+b)*aa + (a+b)*bb both define the strings ending in aa or bb.
Rules for determining RE for a given language defined on a set?
The language of an RE is defined recursively: a single letter x defines {x} and Λ defines {Λ}; if r1 defines L1 and r2 defines L2, then r1r2 defines the product L1L2, r1 + r2 defines L1 ∪ L2, and r1* defines L1*. So every RE has a language built up alongside the expression.
What is EVEN - EVEN LANGUAGE?
EVEN-EVEN is the language over {a,b} of strings with an even number of a's and an even number of b's (Λ included). Reading a word in pairs: aa and bb keep both counts even, while ab or ba change both parities and must be balanced by another ab or ba. RE: (aa + bb + (ab+ba)(aa+bb)*(ab+ba))*.
What is tokenizing string?
Tokenizing a string means splitting it into its letters (tokens) of the alphabet, e.g. over Σ = {a, bb} the string abba is tokenized as a, bb, a. A valid alphabet guarantees a unique tokenization.
What is whole star?
Applying * to a whole (bracketed) regular expression, (r)*, gives all strings formed by concatenating zero or more words of r, including Λ. Example: (ab + b)* = {Λ, ab, b, abb, bab, ...}.
How to use + operator in Automata?
In a regular expression, + between two expressions means union (a choice of either), e.g. a + b. As a superscript, r+ means one or more repetitions of r, the same as r* without the automatic Λ (r+ = rr*).
How to know what is RE?
Generate the shortest strings the RE produces, look at the pattern they share (start, end, length, counts) and describe that set in words; practice with simple REs first.
Why we use null string in FA?
Λ is handled only when it belongs to the language: an FA accepts Λ exactly when its initial state is also a final state. It is not compulsory otherwise.
What is tree structure?
A tree is a connected graph with no cycles. In CFG work, a derivation tree has the start symbol at the root, nonterminals as internal nodes, and terminals (or Λ) at the leaves; reading the leaves left to right gives the derived word.
What is difference between (a, b) & (a + b)?
(a + b) is a regular expression meaning either a or b; (a, b) is only a list of elements (as in Σ = {a, b}), not RE notation.
Difference between FA & TG?
FA: one start state, exactly one single-letter edge for each letter from every state, no Λ-edges. TG: may have several start states, Λ-edges, edges labeled by strings, and missing or several edges for a letter.
Difference between (a+b)+ and (a+b)*?
(a+b)* is all strings over {a,b} including Λ (zero or more repetitions). (a+b)+ is all strings over {a,b} of length at least one (one or more repetitions), so it excludes Λ.
What is length of string?
The length of a string is the number of letters in it, written length(w) or |w|; e.g. length(0101) = 4, length(aa) = 2, length(Λ) = 0. With multi-symbol letters, length counts letters, not symbols.
After looking the on diagram how can we say it is TG or is FA?
Check the FA conditions: exactly one start state, every state has exactly one outgoing edge for each letter of the alphabet, all edges are labeled with single letters and there are no Λ-edges. If any condition fails (several starts, string or Λ labels, missing or repeated letter edges) it is a TG but not an FA.
Differentiate between FA, TG and GTG?
FA: one start state, exactly one single-letter edge per letter from each state. TG: one or more start states, edges labeled with strings or Λ, not all letters required. GTG: like a TG but edges labeled with regular expressions.
Difference between containing and consisting?
A language of strings containing r means r must appear somewhere in the string and the rest can be anything, e.g. containing aa: (a+b)*aa(a+b)*. Consisting of r means the strings are made only of r, nothing else, e.g. consisting of aa: (aa)*.
Define the main formula of Regular expressions? Define the back ground of regular expression?
A regular expression R over Σ is: a letter a in Σ (language {a}); Λ (language {Λ}); R1 + R2 (union); R1R2 (concatenation); R* (closure); or (R). Regular expressions are a declarative notation for the same languages that finite automata accept (Kleene's theorem); they are used in tools such as grep and lex. Example: (00+11)* = {Λ, 00, 11, 0000, 0011, ...}.
Are S* and S+ same?
No. S* always contains Λ, while S+ = SS* contains Λ only if Λ is in S. Example: with S = {a, bb, bab, abaab}, Λ is in S* but not in S+; also abbabaabab is in neither, since it cannot be split completely into words of S.
What is set?
A set is a well-defined collection of distinct objects, called its elements, e.g. {a, b} or {1, 2, 3}.
How many Methods of defining the languages?
Common methods: descriptive definition (in words), listing the words in a set, mathematical (set-builder) notation, recursive definition, regular expression, finite automaton, transition graph and context-free grammar.
What is difference between Palindrome, Kleene star closure and plus operation?
PALINDROME is the language of Λ and all strings s with Rev(s) = s. Kleene star Σ* is the set of all concatenations of zero or more elements of Σ, including Λ. PLUS Σ+ is the set of concatenations of one or more elements, so it does not automatically contain Λ.
What is inside language?
A language is a set of words (strings) over an alphabet, together with the rule that decides which strings belong to it.
What is Equal RE?
Different REs that define the same language are called equivalent (equal) REs, e.g. (a+b)*(aa+bb) and (a+b)*aa + (a+b)*bb.
How can we make Finite Automaton from a language and a language from FA?
There is no fixed formula for designing an FA from a language: decide what each state must remember, then draw the states and transitions and test them. To find the language of an FA, trace which strings lead from the initial state to final states and describe them, or convert the FA into an RE using Kleene's theorem (via TG/GTG state elimination).
Could we just use +, - symbols with x not with y in FA?
Yes. State names (x1, y1, q0, ...) are arbitrary; '-' marks the initial state and '+' marks final states and can be put on any state. If they are not used, the initial state must be shown another way (an arrow) and final states another way (a double circle).
Explain the language L of string, defined over Σ = {0,1}, having double 0's and double 1's?
In the handouts this means strings that contain at least one double letter 00 or 11 as a substring: RE (0+1)*(00+11)(0+1)*. The shortest words are 00 and 11; Λ, 0, 1, 01, 10, 010 are not in the language.
What are the difference between single 1 and 0 and double 1's and 0's?
Strings having single 0's or 1's (any letters, no null) are given by (0+1)+, whose shortest words are 0 and 1. Strings having double 0's or double 1's must contain 00 or 11 together somewhere: (0+1)*(00+11)(0+1)*, whose shortest words are 00 and 11.
On what basis we select initial and final states?
The initial state is where processing of every string begins. Final states are those states in which the machine ends exactly when the string read so far belongs to the language; so the choice follows from what each state represents for the given language (and the initial state is final if Λ is in the language).
How we know that the given expression has how many states?
There is no fixed formula; the number of states depends on how much information about the input read so far must be remembered to decide membership. Each distinct situation needs a state (plus a dead state if needed).
How will we develop the rules of transition?
For each state and each letter, decide which situation the machine is in after reading that letter, and draw an edge to that state. In an FA every state needs exactly one transition for each letter.
Can we accept the strings going from final to initial?
No. A string is accepted only if, starting at the initial state and reading the string from left to right, the machine ends in a final state. Paths from a final state back to the initial state do not count; if no final state is reachable from the initial state, the FA accepts nothing, not even Λ.
What are the basic rules to build FA?
An FA for a language must accept every word of the language and reject every other string; it must have one initial state and exactly one transition for each letter from every state. A language can have many different correct FAs.
What is Dead state?
A dead (trap) state is a non-final state from which every letter leads back to itself, so once entered the string can never be accepted. It is used to make an FA complete (a transition for every letter) without changing the language.
Stack consistence means that in the PDA?
In a PDA (in conversion form), a path is stack consistent if each POP along it finds on top of the STACK exactly the character its edge requires; a row can pop only the character actually on top.
Where Null string is use the most?
Λ is used wherever a language must include the empty word or a machine must move without reading input: in Kleene star closure (r* always contains Λ), in accepting Λ in an FA by making the initial state final, as Λ-edges in TGs and NFAs (e.g. when combining machines in Kleene's theorem), and as null productions N → Λ in CFGs.
PUSHDOWN AUTOMATON (PDA)?
A PDA is an FA with a PUSHDOWN STACK (store) as memory. It has an input alphabet, an input TAPE, a stack alphabet, a STACK that is initially empty (blanks) and can hold any number of letters, a START state, ACCEPT and REJECT states, READ states (read the next input letter), PUSH states (put a letter on top of the STACK) and POP states (remove the top letter). PDAs accept the context-free languages.
Prefixes of a language in another language?
For languages Q and R, Pref(Q in R) is the set of all strings p such that pq = w for some word q in Q and some word w in R, i.e. the beginnings of words of R that are completed by a word of Q. Example: Q = {aa, abaaabb, bbaaaaa, bbbbbbbbbb}, R = {b, bbbb, bbbaaa, bbbaaaaa}; bbbaaa = bbba·aa, bbbaaaaa = bbbaaa·aa = b·bbaaaaa, so Pref(Q in R) = {b, bbba, bbbaaa}. If R is regular, Pref(Q in R) is regular.
Conversion form of PDA?
A PDA is in conversion form if: (1) there is only one ACCEPT state; (2) there are no REJECT states; (3) every READ or HERE is immediately followed by a POP; (4) no two POPs occur in a row on a path without a READ or HERE between them; (5) all branching occurs at READ or HERE states, none at POP states, and every edge has one label; (6) a bottom-of-stack symbol $ is pushed before START's processing and is never popped beneath, being popped only just before ACCEPT; (7) the whole input is read before accepting.
Is automata is a programming subject or theoretical?
It is theoretical. Automata theory studies abstract machines (automata) and the formal languages they recognize, and what problems they can solve. Its results are applied in compilers, parsers and text processing, but the subject itself is not programming.
How can we define languages elaborate any five ways.
(1) Descriptive definition: state the rule in words, e.g. strings of even length. (2) Listing / set notation, e.g. L = {Λ, aa, ab, ba, bb, aaaa, ...}. (3) Recursive definition: base words, rules to build more words, nothing else. (4) Regular expression, e.g. ((a+b)(a+b))*. (5) Finite automaton (or TG) that accepts exactly the words. Also context-free grammars.
Describe the POP operation and draw symbol for POP state in context of Push down stack.
POP takes the top character off the STACK; the remaining characters move up one place. The POP state is drawn as a diamond-shaped box labeled POP, with one outgoing edge for each stack character that may be on top (including Δ for an empty stack); the machine follows the edge labeled with the character popped.
Concept of unit production in CFG?
A unit production has the form nonterminal → one nonterminal, e.g. S → A. It can be removed without changing the language: delete S → A and, for each non-unit production A → w, add S → w (following chains of unit productions). Unit productions are removed when converting to CNF.
Consider the language L which is EVEN-EVEN, defined over Σ = {a,b}. In how many classes does L may partition Σ*. Explain briefly.
L = EVEN-EVEN partitions Σ* into four classes, according to the parity of the numbers of a's and b's: C1 = even a's and odd b's; C2 = odd a's and odd b's; C3 = odd a's and even b's; C4 = even a's and even b's (= L). Strings in the same class are indistinguishable with respect to L, strings in different classes are distinguishable, so the minimal FA for EVEN-EVEN has four states.
If two FA have no final state how the intersection of those FA will have final state?
It will not have one. In the intersection FA a state (pair of states) is final only if both of its components are final; since neither FA has a final state, no pair is final, so the intersection FA has no final state and accepts nothing (the empty language).
give RE for EVEN - EVEN language.
(aa + bb + (ab + ba)(aa + bb)*(ab + ba))*
use of push and pop states
PUSH x places the letter x on top of the STACK, moving the other letters down; POP removes the top letter of the STACK and the machine branches according to which letter was removed (Δ if the stack is empty). Together they let a PDA store input letters and compare them later, e.g. push a's then pop one for each b to accept a^n b^n.
Write point of kleen's theorem?
Kleene's theorem: if a language can be expressed by an FA, a TG or an RE, then it can be expressed by the other two as well. It is proved in three parts: Part I, every FA is a TG; Part II, every TG can be converted to an RE; Part III, every RE can be converted to an FA.
What is meant by decidable problem?
A problem is decidable if there is a decision procedure (algorithm) that always gives the correct yes/no answer in a finite number of steps. Examples: whether two regular expressions define the same language; whether two FAs are equivalent; whether an FA accepts any word.
Define strings. With example.
A string is a concatenation of a finite number of letters from an alphabet. Example: over Σ = {a, b}, a, ab, bba and abab are strings; Λ is the string with no letters.
Write regular expression contain even words defined over sigma={a, b}
((a+b)(a+b))* (all strings of even length, including Λ)
Explain Semi word and word with example?
A word is a string of terminals only (Λ is also a word), e.g. aaaa from S → aaaa. A semiword is a string of zero or more terminals followed by exactly one nonterminal at the right, of the form (terminal)...(terminal)(nonterminal), e.g. aaaaS from S → aaaaS.
Differentiate b/w FA, TG and GTG?
FA: finite states with exactly one initial state and some final states; finite alphabet; for every state and every letter exactly one transition, labeled by a single letter. TG: finite states, at least one initial state and some final states; transitions labeled by strings of letters or Λ, not necessarily for every letter. GTG: finite states, at least one initial state and some final states; edges labeled by regular expressions.
Can we accept the string going from final to initial state?
No. To accept a string the machine must start at the initial state and, reading the string, reach a final state; to test whether an FA accepts any word we look for paths from the initial state to a final state.
State uses of PDA in computing?
A PDA gives the theoretical model of computation with a stack memory: it recognizes context-free languages and is the basis of parsers (syntax analysis) in compilers, e.g. checking balanced parentheses and nested expressions.
If there is no initial state in FA then that FA does not accept any language. Discuss two situations when an FA does not accept any string not even the null string?
(1) The FA has no final state, so no path can end in a final state. (2) The FA has final states, but none of them can be reached from the initial state (the final states are disconnected from it). In both cases the FA accepts no string, not even Λ (Λ is accepted only if the initial state is final).
Describe unit production in detail?
A unit production has the form nonterminal → one nonterminal, e.g. S → A. It can be removed without changing the language: delete S → A and, for each non-unit production A → w, add S → w (following chains of unit productions). Unit productions are removed when converting to CNF.
Push and pop operation?
PUSH x places the letter x on top of the STACK, moving the other letters down; POP removes the top letter of the STACK and the machine branches according to which letter was removed (Δ if the stack is empty). Together they let a PDA store input letters and compare them later, e.g. push a's then pop one for each b to accept a^n b^n.
Difference between push down stack and push down store?
There is no difference; both names denote the same memory of a PDA, a place where input letters can be stored (on top of each other) and later removed from the top. It can hold any number of letters and is initially empty (all blanks).
Five conditions of PDA conversion?
A PDA is in conversion form if: (1) there is only one ACCEPT state; (2) there are no REJECT states; (3) every READ or HERE is immediately followed by a POP; (4) no two POPs occur in a row on a path without a READ or HERE between them; (5) all branching occurs at READ or HERE states, none at POP states, and every edge has one label; (6) a bottom-of-stack symbol $ is pushed before START's processing and is never popped beneath, being popped only just before ACCEPT; (7) the whole input is read before accepting.
what is POP stake and draw it diagram.
POP takes the top character off the STACK; the remaining characters move up one place. The POP state is drawn as a diamond-shaped box labeled POP, with one outgoing edge for each stack character that may be on top (including Δ for an empty stack); the machine follows the edge labeled with the character popped.
Consider the following CFG: S → aXb | bXa, X → aX | bX | Λ. What does it mean?
It generates the language over {a,b} of strings that begin and end with different letters: X generates any string (a+b)*, so S gives a(a+b)*b or b(a+b)*a.
Explain Distinguishable strings and Indistinguishable strings?
Two strings x and y are distinguishable with respect to a language L if there is some string z such that exactly one of xz and yz is in L. They are indistinguishable if for every string z, xz is in L if and only if yz is in L. Example for L = strings ending in a: a and b are distinguishable (z = Λ: a is in L, b is not); a and ba are indistinguishable.
What is Row Language?
For a PDA in conversion form, its summary table lists the rows (path segments between joints). The row language is the language over the alphabet of row names {Row1, Row2, ...} whose words are the sequences of rows that form complete paths from START to ACCEPT that are joint consistent and stack consistent. A CFG is built for this row language and then turned into a CFG for the language of the PDA.
What does FA stands for?
FA stands for Finite Automaton (plural: finite automata).
What do you mean by wanted and unwanted branches?
In top-down parsing, wanted branches are the branches of the derivation tree that can lead to the required word; unwanted branches are those that cannot lead to it and are dropped.
Who invented Turing m/c
Alan Mathison Turing (1936).
Equivalent / non-equivalent languages
Two languages are equivalent if they contain exactly the same words; otherwise they are non-equivalent. For regular languages L1 and L2 this is decidable: build an FA for (L1 ∩ L2') ∪ (L1' ∩ L2), the words in exactly one of them. If this FA accepts no word, L1 and L2 are equivalent; if it accepts some word, they are not.
What are formal languages?
Formal languages are languages defined only by precise syntactic rules over an alphabet (which strings are words), without regard to meaning. Example: EVEN-EVEN over {a,b}. They are studied in automata theory, unlike informal (natural) languages.
What is Transition?
A transition is a move of the machine from one state to another on reading an input letter; in an FA there is a transition for every state and every letter.
Alternative form of this production: Σ = {a,b}, productions: S → aS | bS | a | b | Λ
This grammar generates (a+b)*, all strings over {a,b}. An equivalent shorter form is S → aS | bS | Λ (S → a and S → b are not needed since aS ⇒ a using S → Λ).
What is input Tap?
The input TAPE of a PDA (or TM) is where the input string is placed before running. It is divided into cells, one letter per cell, starting from the first cell; the cells after the input contain blanks (Δ). The machine reads letters from it one by one.
What is live production?
A live production has the form nonterminal → string of two nonterminals, e.g. A → BC.
Differentiate between Distinguishable and Indistinguishable strings.
Two strings x and y are distinguishable with respect to a language L if there is some string z such that exactly one of xz and yz is in L. They are indistinguishable if for every string z, xz is in L if and only if yz is in L. Example for L = strings ending in a: a and b are distinguishable (z = Λ: a is in L, b is not); a and ba are indistinguishable.
What is wanted and unwanted branches
In top-down parsing, wanted branches can lead to the required word; unwanted branches cannot and are discarded.
Define two rules (Row Language).
Rules for the CFG of the row language: Rule 1: S → Net(START, ACCEPT, $). Rule 2: for every row from joint X to joint Y that pops w and pushes nothing, Net(X, Y, w) → that row. Rule 3: for every row from X to Y that pops w and pushes u1...un, Net(X, Z, w) → row Net(Y, A1, u1) Net(A1, A2, u2) ... Net(An-1, Z, un) for all possible joints A1, ..., An-1, Z.
ambiguous grammer
A CFG is ambiguous if at least one word of its language has two or more different derivation trees (equivalently, two different leftmost derivations). Example: S → S+S | S*S | number gives two trees for 3+4*5.
Difference between semi-word and word with example?
A word is a string of terminals only, e.g. abba; a semiword is terminals followed by exactly one nonterminal at the right, e.g. abbA.
If there are more than one edges between two states then we can replace them by one edge in a TG. Explain it with examples?
If there are several edges from state x to state y (or several loops at a state) labeled r1, r2, ..., they can be replaced by a single edge labeled r1 + r2 + ..., because the machine can follow any one of them. Example: edges from x to y labeled a and bb become one edge labeled a + bb; loops a and b at a state become one loop labeled a + b. The result is a GTG accepting the same language (a step in Kleene's theorem Part II).
How can you say that two FAs are equivalent?
Two FAs are equivalent if they accept the same language. It can be checked by building the FA for (L1 ∩ L2') ∪ (L1' ∩ L2); if it accepts no word, the FAs are equivalent.
What is a production?
A production is a grammatical rule of a CFG, of the form nonterminal → string of terminals and/or nonterminals.
If L1, L2 and L3 be any three finite languages over Sigma = {a,b}, then how will be (L1 ∩ L2) ∪ (L2 ∩ L3) ≠ Ø
It is not always true. (L1 ∩ L2) ∪ (L2 ∩ L3) is non-empty exactly when L2 has at least one word in common with L1 or with L3. If L2 shares no word with L1 and no word with L3, the expression equals Ø.
similarity and dif b/w DFA and NFA
Differences: (1) in a DFA each state has exactly one transition for each letter; in an NFA a state may have several transitions for the same letter or none; (2) a DFA has a single possible path for a string, an NFA may have many, and accepts if any path ends in a final state (an NFA may also allow Λ-moves). Similarities: (1) both have a finite set of states, a finite input alphabet, one initial state and some final states; (2) both accept exactly the regular languages, since every NFA can be converted to an equivalent DFA.
RE for Even-even
(aa + bb + (ab + ba)(aa + bb)*(ab + ba))*
Differentiate between Regular and Non regular languages?
A regular language can be expressed by a regular expression (equivalently accepted by an FA). A nonregular language cannot be expressed by any regular expression, e.g. {a^n b^n}.
What is meant by a "Transition" in FA?
A transition is the move from one state to another on reading a letter; an FA has exactly one transition for each state and each letter.
What are the halt states of PDAs?
The halt states of a PDA are ACCEPT and REJECT. Reaching ACCEPT means the input string is accepted; reaching REJECT (or crashing) means it is rejected. They have in-edges but no out-edges.
Identify the null productions and nullable productions from the following CFG: S → ABAB, A → a | Λ, B → b | Λ
Null productions: A → Λ and B → Λ. Nullable nonterminals: A, B and also S, because S → ABAB can derive Λ; so S → ABAB is a nullable production.
Alternative form of this production S → aS, S → bS, S → Λ.
The productions can be written in one line as S → aS | bS | Λ. This grammar generates (a+b)*, all strings over {a,b} including Λ.
What are living and dead productions?
A live production has the form non-terminal → string of two non-terminals (e.g. S → XY); a dead production has the form non-terminal → terminal (e.g. A → a). They are used in the pumping lemma for CFLs.
Can you say that string of 0's whose length is a perfect square is not regular?
Yes. SQUARE = {0^(n^2)} is not regular: the gaps between consecutive perfect squares grow without bound, so pumping any y gives lengths that are not squares, contradicting the pumping lemma.
If L is the language that accept even length strings then what strings will Lc accept?
Lc contains all strings of odd length over the same alphabet (e.g. (a+b)((a+b)(a+b))*). Λ has even length, so it is in L, not Lc.
Define Myhill Nerode theorem.
Myhill-Nerode theorem: a language L over Σ partitions Σ* into distinct classes of indistinguishable strings. (1) If L is regular, L generates a finite number of classes. (2) If L generates a finite number of classes, L is regular. So L is regular exactly when the number of classes is finite.
If L1,L2 and L3 be any three finite languages over Sigma = {a,b}, then how will be (L1 INTERSECTION L2) Union (L2 INTERSECTION L3) ≠ Ø
The language (L1 ∩ L2) ∪ (L2 ∩ L3) is non-empty exactly when L2 shares at least one word with L1 or with L3. If L2 has no word in common with either L1 or L3, both intersections are empty and the union is Ø. So the statement holds only in the first case.
How you differentiate between wanted and unwanted branches while deriving a string from in the context of CFG?
In top-down parsing we grow the derivation tree from S. A branch whose working string can still derive the target word (its terminal prefix matches and its length does not exceed the word) is wanted; a branch that can no longer produce the word is unwanted and is cut off.
If L1,L2 and L3 be any three finite languages over Sigma = {a,b}, then how will be (L1 ∩ L2) U (L2 ∩ L3) ≠ Ø
It is non-empty exactly when L2 shares at least one word with L1 or with L3. If L2 has no word in common with L1 and none with L3, both intersections are empty and the union is Ø.
What is meant by "Left most Derivation" in context of CFG?
A leftmost derivation is a derivation in which, at every step, the production is applied to the leftmost nonterminal in the current working string. Each word generated by a CFG has a leftmost derivation; for example with S → SS | a, S ⇒ SS ⇒ aS ⇒ aa always replaces the leftmost S first.
Explain the language L of string, defined over Σ = {0,1}, having double 0's or double 1's?
L is the set of all strings over {0,1} that contain the substring 00 or the substring 11 somewhere (for example 00, 11, 1001, 0110). Strings in which 0s and 1s strictly alternate, such as Λ, 0, 1, 01, 1010, are not in L. A regular expression for L is (0+1)*(00+11)(0+1)*.
Consider the language defined by the following regular expression: b(a + b)*a What will be the corresponding Context Free Grammar (CFG)?
The language is all strings over {a,b} that start with b and end with a. A CFG: S → bXa, X → aX | bX | Λ. Here X generates (a+b)*, and S puts b in front and a at the end.
Consider live productions to be applied during derivation of a word. In your point of view what will be the ultimate result?
A live production has the form N → NN (one nonterminal replaced by two), so each time it is applied the number of nonterminals in the working string increases by one. Only dead productions (N → terminal) remove nonterminals. If only live productions were applied, the derivation would never end in a word. To derive a word of n letters in CNF, exactly n − 1 live productions and n dead productions are applied; in a long enough word some live production must be repeated, which is the basis of the pumping lemma for CFLs.
What is meant by the following statement? "LANGUAGE IS CLOSED"
A class of languages is closed under an operation if applying that operation to languages of the class always gives a language that is again in the class. For example, regular languages are closed under union, concatenation, Kleene star, complement and intersection: if L1 and L2 are regular, then L1 + L2, L1L2, L1*, L1ᶜ and L1 ∩ L2 are also regular. Context free languages are closed under union, concatenation and Kleene star, but not under intersection or complement.
Write three different parsing techniques.
1) Top-down parsing: start from the start symbol and apply productions to try to derive the given word (for example by building the derivation tree from the root). 2) Bottom-up parsing: start from the word and replace right-hand sides by their left-hand nonterminals until only the start symbol remains. 3) The CYK algorithm: for a grammar in CNF, fill a table of the nonterminals that generate every substring of the word, and accept if the start symbol generates the whole word.
Illustrate Decidable Problem with the help of an example. Marks [1+2]
A problem is decidable if there is an algorithm (effective procedure) that always halts in a finite number of steps and gives the correct yes or no answer for every input. Example: "Does a given FA accept any word?" is decidable. If the FA has N states, test all strings of length less than N; if none of them is accepted, the FA accepts no word at all, otherwise its language is not empty. Similarly, whether two regular expressions define the same language is decidable, by building FAs for (L1 ∩ L2ᶜ) + (L2 ∩ L1ᶜ) and testing that it accepts nothing.
Write alternative form of this production. S → aS, S → bS, S → Λ
The three productions can be written together with the bar symbol as S → aS | bS | Λ. This grammar generates (a+b)*.
What is meant by Row language?
When a PDA is put in conversion form, its paths between joints are listed as rows of a summary table. The row language is the language whose alphabet is the set of row names, Σ = {Row1, Row2, …, Rown}. Its words are the sequences of rows that correspond to complete paths from START to ACCEPT that are consistent with the stack (each row pops what the previous rows pushed). A CFG for this row language is used in proving that every PDA language is context free.
Write down regular expression for a language L of strings defined over Σ = {a, b} that neither ends in "a" nor with "b".
Every non-empty string over {a,b} ends in either a or b, so the only string that ends in neither is the null string. Hence L = {Λ} and its regular expression is Λ.
What does the following arbitrary summary table show? FROM Where: READ9 | TO Where: READ3 | READ What: b | POP What: b | PUSH What: abb | ROW Number: 11
It is Row11 of the summary table of a PDA in conversion form. It describes the path segment that starts at READ9, reads the letter b, pops b from the STACK, pushes abb, and ends at READ3. This row is not a "Net-style" path, because it does not just consume one stack letter: it pops one letter and pushes three, so the stack grows by two letters. Row11 can therefore only be used together with other Net-style pieces that remove those letters, e.g. Net(READ9, READ8, b) → Row11 Net(READ3, READ7, a) Net(READ7, READ1, b) Net(READ1, READ8, b), which becomes a production in the CFG for the row language.
Write down Context Free Grammar (CFG) for the language of strings expressed by the following regular expression: (a + b)*(a + b)*
(a+b)*(a+b)* defines the same language as (a+b)*, i.e. all strings over {a,b} including Λ. A CFG is S → aS | bS | Λ.
What does the following arbitrary summary table show? FROM Where: READ0 | TO Where: READ1 | READ What: b | POP What: b | PUSH What: abb | ROW Number: 11
It is one row (row number 11) of the summary table of a PDA in conversion form. It shows a path segment that starts at the joint state READ0 and ends at the joint state READ1; along this segment the PDA reads the letter b from the input tape, pops b from the stack, and then pushes the string abb onto the stack. Each such row can later be used as a letter of the row language when building a CFG from the PDA.
Parsing Techniques
Parsing means finding a derivation (tree) of a given word from a CFG. Top-down parsing starts from the start symbol and expands productions, discarding branches that cannot lead to the word; bottom-up parsing starts from the word and reduces substrings to nonterminals until the start symbol is reached. The ambiguous grammar S → S+S | S*S | number gives two values for 3+4*5 (23 or 35); the unambiguous PLUS-TIMES grammar S → E, E → T+E | T, T → F*T | F, F → (E) | i gives * priority over +. Derivation of i+i*i: S ⇒ E ⇒ T+E ⇒ F+E ⇒ i+E ⇒ i+T ⇒ i+F*T ⇒ i+i*T ⇒ i+i*F ⇒ i+i*i.
What are live and dead productions.
In a CFG in CNF, a live production has the form nonterminal → string of two nonterminals (e.g. S → AB); it keeps the derivation going. A dead production has the form nonterminal → terminal (e.g. A → a); it ends that branch. Every derivation of a word uses live productions to grow the working string and dead productions to finish it.
While converting mealy to Moore num of states remain same or not? justify
Not necessarily; the number of states may increase. In the conversion, the output of each incoming edge of a Mealy state is moved onto the state. If all edges entering a state carry the same output, the state is kept with that output. If they carry different outputs, the state is split into one copy for each different output (q becomes q1, q2, ...), each copy having the same outgoing edges as q. So the Moore machine has the same number of states only when no state has incoming edges with different outputs; otherwise it has more. (The Moore machine prints one extra first character, which is ignored for equivalence.)
a) Write RE defined over Σ = {a, b} strings not ending on aa, ab.
The strings not ending in aa or ab are those whose second-last letter is b, plus the strings of length less than 2: Λ + a + b + (a+b)*(ba + bb).
b) Write RE defined over Σ = {a, b} strings must end on aa, ab
(a+b)*(aa + ab), i.e. (a+b)*a(a+b)
Explain CFG and even-even language.
A CFG consists of an alphabet Σ of terminals, a set of nonterminals including the start symbol S, and a finite set of productions of the form nonterminal → finite string of terminals and/or nonterminals; its language is all terminal strings derivable from S. EVEN-EVEN is the language over {a,b} of strings with an even number of a's and an even number of b's. A CFG for it: S → SS | XS | YSY | Λ, X → aa | bb, Y → ab | ba. Another: S → aaS | bbS | abX | baX | Λ, X → aaX | bbX | abS | baS.
Prove kleens theorem part two?
Part II: every TG can be converted to an RE. Proof by algorithm: (1) If the TG has several start states, add a new unique start state with Λ-edges to them; if it has several final states, add a new unique final state with Λ-edges from them; make the start state have no incoming edges and the final state no outgoing edges. Edges may now be labeled with REs (GTG). (2) Replace all edges between the same pair of states (in the same direction, including loops) by one edge labeled with the sum of their labels. (3) Eliminate the other states one by one: for a state with a loop labeled r2, every path entering with r1 and leaving with r3 is replaced by a direct edge labeled r1 r2* r3 (r1 r3 if no loop), then combine parallel edges again. (4) When only the start and final states remain, the label of the edge between them is an RE for the language of the TG.
Construct corresponding CFG for the given language: (1) All words of even length but not multiple of 3.
Over {a,b}, the lengths allowed are 2, 4, 8, 10, 14, 16, ... (length ≡ 2 or 4 mod 6). CFG: S → XXXXXXS | XX | XXXX, X → a | b.
Construct corresponding CFG for the given language: (2) Palindrome (both even and odd palindrome).
S → aSa | bSb | a | b | Λ. The productions aSa and bSb add the same letter at both ends; a or b ends an odd palindrome and Λ ends an even one.
two different method for converting the NFA to FA
Method 1: an NFA is also a TG, so find an RE for it using Kleene's theorem Part II, then build an FA from that RE using Part III. Method 2 (subset construction): start from the initial state of the NFA; each state of the new FA represents a set (combination) of NFA states; for each letter, the next FA state is the set of all NFA states reachable on that letter; where there is no transition use an empty (dead) state; a set is final if it contains a final NFA state. Continue until no new sets appear.
Explain the decidability and examples.
A problem is effectively solvable if an algorithm gives its answer in a finite number of steps (e.g. solving a quadratic equation with the quadratic formula). A yes/no problem with such a decision procedure is decidable. Examples for regular languages: whether two REs (or two FAs) define the same language (build the FA for (L1 ∩ L2') ∪ (L1' ∩ L2) and test if it accepts anything); whether an FA accepts any word (look for a path from the initial to a final state, or test all strings shorter than the number of states); whether an FA accepts infinitely many words (test strings of length N to 2N-1). Problems with no such algorithm are undecidable.
What are the conditions (any five) that must be met to know that PDA is in conversion form?
A PDA is in conversion form if: (1) there is only one ACCEPT state; (2) there are no REJECT states; (3) every READ or HERE is immediately followed by a POP; (4) no two POPs occur in a row on a path without a READ or HERE between them; (5) all branching occurs at READ or HERE states, none at POP states, and every edge has one label; (6) a bottom-of-stack symbol $ is pushed before START's processing and is never popped beneath, being popped only just before ACCEPT; (7) the whole input is read before accepting.
Differentiate Live Production, Dead Production
A live production has the form nonterminal → string of two nonterminals (e.g. A → BC); it increases the number of nonterminals in the working string. A dead production has the form nonterminal → terminal (e.g. A → a); it removes a nonterminal. In a CNF derivation of a word with n letters, live productions are used n - 1 times and dead productions n times.
Construct corresponding CFG for the given language: All words of even length but not multiple of 3.
Even length but not a multiple of 3 means length 6k+2 or 6k+4. Over {a,b}: S → YS | XX | XXXX, Y → XXXXXX, X → a | b. Each Y adds 6 letters and the end adds 2 or 4.
Construct corresponding CFG for the given language: Palindrome (both even and odd palindrome).
S → aSa | bSb | a | b | Λ. The rules aSa and bSb add the same letter at both ends; ending with a or b gives odd palindromes and ending with Λ gives even palindromes.
What is the difference between concatenation and intersection of two FAs and union and addition of two FAs?
Union and addition are the same thing: FA1 + FA2 accepts words accepted by either machine; its states are pairs and a state is final if either component is final. Intersection accepts words accepted by both machines; the same pair construction is used but a state is final only if both components are final. Concatenation FA1FA2 accepts words that split as w = xy with x accepted by FA1 and y by FA2; when a final state of FA1 is reached, the initial state of FA2 is added as a possibility, and a state is final if it contains a final state of FA2.
Write RE defined over Σ = {a, b} strings must end on aa,ab
(a+b)*(aa+ab), which is the same as (a+b)*a(a+b).
Derive Chomsky Normal Form (CNF) corresponding to the Context Free Grammar (CFG) given below: A → BAB | B | Λ B → 00 | Λ
A and B are both nullable. Removing the Λ-productions (CNF generates the language without Λ) gives A → BAB | AB | BA | BB | B and B → 00 (A → A is dropped). Removing the unit production A → B gives A → BAB | AB | BA | BB | 00, B → 00. Now replace the terminal 0 by Z → 0 and break the long right side using R → AB. The CNF is: A → BR | AB | BA | BB | ZZ; R → AB; B → ZZ; Z → 0.
Write the CFG for EVEN-EVEN language?
EVEN-EVEN (even number of a's and even number of b's) is generated by: S → SS | BALANCED S | S BALANCED | UNBALANCED S UNBALANCED | Λ; BALANCED → aa | bb; UNBALANCED → ab | ba. A BALANCED pair keeps both counts even; two UNBALANCED pairs (ab or ba) together add one a and one b each, so both counts stay even. An equivalent shorter form is S → SS | XS | YSY | Λ, X → aa | bb, Y → ab | ba.
Using suitable examples, differentiate between Kleene star closure and plus operation?
The Kleene star closure Σ* of an alphabet (or set of strings) is the set of all strings formed by concatenating any number of its elements, including zero elements, so it always contains Λ. Example: if Σ = {x}, then Σ* = {Λ, x, xx, xxx, …}; if Σ = {0,1}, then Σ* = {Λ, 0, 1, 00, 01, 10, 11, …}. The plus operation Σ⁺ is the same except that at least one element must be used, so Λ is not generated automatically: if Σ = {0,1}, Σ⁺ = {0, 1, 00, 01, 10, 11, …}. Thus Σ* = Σ⁺ + {Λ} (and Λ is in Σ⁺ only if Λ is itself in Σ). Both give infinite languages for a non-empty alphabet.
a. Construct Context Free Grammar (CFG) for the language defined by the regular expression: (ab + ba)*(a + b)* b. Remove null productions from the CFG constructed in part i.
a) S → XY; X → abX | baX | Λ; Y → aY | bY | Λ. X generates (ab+ba)* and Y generates (a+b)*. b) The nullable nonterminals are X, Y and S. Adding every production with nullable nonterminals left out and deleting the Λ-productions gives: S → XY | X | Y; X → abX | baX | ab | ba; Y → aY | bY | a | b. This grammar generates the same language except the null string Λ.