Σ={a,Aa,Abb}, then string aAaAbbAa has ________ length.
- AOne
- BTwo
- CThree
- DFour
The string tokenizes as a, Aa, Abb, Aa, which is four letters.
Syllabus: lectures 1–24. Past-paper MCQs are shown first.Syllabus: lecture 1–24. Past paper ki MCQs pehle dikhai gayi hain.
55 MCQs · 45 short · 9 long questions · 55 MCQs from past papers55 MCQs · 45 short · 9 long sawal · 55 MCQs past papers se
Σ={a,Aa,Abb}, then string aAaAbbAa has ________ length.
The string tokenizes as a, Aa, Abb, Aa, which is four letters.
If an alphabet has n number of letter, then number of strings of length m will be
Each of the m positions has n choices, giving n^m strings.
Auto Meta mean
Automata comes from a word meaning self-acting or automatic.
Σ = {a,bc,cc} has the letters
The alphabet lists three letters: a, bc and cc.
Length of strings, generated by infinite language is_______
An infinite language has infinitely many words, but each word has finite length.
Length of null string is
The null string Λ has no letters, so its length is 0.
Which statement is true?
Words are strings that belong to a language, so every word is a string but not the reverse.
Which of the following is not a word of language EQUAL?
abababa has four a's and three b's, so it is not in EQUAL.
In which of the following language Rev(s)=s
PALINDROME is the language of words equal to their own reverse.
Languages generated by kleene star are always ______________.
As taught, the closure of a set with a non-null string contains infinitely many strings.
Let S = {aa, bb} be a set of strings then s* will have
S* always contains Λ, and the other strings cannot be split into aa and bb.
If S = {aa, bb}, then S* will not contain..
aaabbb has an odd run of a's, so it cannot be built from aa and bb.
S = {baa, ab}, then S* will not contain
abbaab splits as ab, baa and a leftover b, so it is not in S*; the others can be split.
If r1 = (aa + bb) and r2 = ( a + b) then the language (aa + bb)* will be generated by
(aa + bb)* is the Kleene star of r1.
RE for the language defined over Σ={a,b} having words starting with a is____
The word must begin with a, followed by any string.
a (a + b)* is the RE of language defined over Σ = {a, b} having at least one a
a(a+b)* only gives words starting with a; ba has an a but is missing.
(a+b)*a(a+b)*b(a+b)* is the RE of language defined over Σ={a,b} having at least one a and one b
This RE needs an a before a b, so words like ba are missing.
a*b* = (ab)* this expression is __________
aab is in a*b* but not in (ab)*, so they differ.
One FA has 3 states and 2 letters in the alphabet. Then FA will have ___________ number of transitions in the diagram
Each of the 3 states needs one transition for each of the 2 letters: 3 × 2 = 6.
Every FA should be __________
An FA has exactly one transition per letter from each state.
In FA final state represent by _________sign
Final states are marked + and the initial state -.
One FA has n states and m letters in the alphabet. Then FA will have _____ number of transitions in the diagram.
Each of the n states has one transition for each of the m letters.
"Every finite language can be expressed by FA". This statement is __________.
Every finite language is regular, so an FA can be built for it.
In TG there may exist more than one path for certain string.
A TG may be nondeterministic, so a string can have several paths.
In TG there may exist no paths for certain string.
A TG need not have an edge for every letter, so some strings have no path.
TG can more then one initial state
A TG may have several start states.
TG is always deterministic.
A TG may have several or no paths for a string, so it can be nondeterministic.
In TG, there may be a transition for null string.
TG edges may be labelled with Λ.
TG can have more than one initial state.
A TG may have several start states.
GTG can have _______________ final state.
A GTG may have no final state, one, or several.
In GTG, if a state has more than one incoming transitions from a state. Then all those incoming transitions can be reduced to one transition using _____________ sign
Parallel edges labelled r1 and r2 become one edge labelled r1 + r2.
In GTG's there may exist no path for a certain string.
Like a TG, a GTG need not have a path for every string.
GTG can have _____________ initial state.
A GTG has at least one start state and may have several.
In NFA, there may be more than one transition for certain letters and there may not be any transition for certain letters. This statement is ______________.
This freedom is what makes an NFA nondeterministic.
If in an NFA, Λ is allowed to be a label of an edge then that NFA is called ________.
Such a machine is called both NFA with null string and NFA with Λ.
Two machines are said to be equivalent if they print the same output string when the different input string is run on them
Machines are equivalent when they print the same output for the same input string.
If a language can be expressed through FA, then it can also be expressed through TG.
Every FA is also a TG (Kleene's theorem part I).
"One language can be expressed by more than one NFA". This statement is ______________.
Many different NFAs can accept the same language.
If a language is expressed through TG, then that language will have its RE.
Kleene's theorem part II: every TG language has an RE.
One language can represents more than one RE.
For example (a+b)* and (a*b*)* define the same language.
The closure FA* (star on an FA) always accept ______string
The closure of any language contains Λ, so FA* accepts the null string.
In FA one enter in specific stat but there is no way to leave it then state is called
A state with no exit is called a dead state, waste basket or Davey John locker.
Using tree structure final state represent by
Besides +, a final state may be drawn as a double circle.
"Every Infinite language is regular" this statement is
Infinite languages such as PALINDROME are not regular.
In drawing FA3 (which is equal to FA1 + FA2), a state will be declared final if
A word is in L1 + L2 if either FA accepts, so a combined state is final if either part is final.
The _______ machine helps in building a machine that can perform the addition of binary numbers.
The incrementing (Mealy) machine is the basis for a binary adder.
"One language can be represented by more than one RE" this statement is____
For example (a+b)* and (a*b*)* define the same language.
If FA1 accepts no string and FA2 accepts many strings, then FA1 + FA2 will be equal to
The union of the empty language with L2 is L2.
"Every Infinite language is regular" this statement is
Infinite languages such as PALINDROME are not regular.
PALINDROME can be defined by more than one regular language
PALINDROME is nonregular, so no RE or regular language defines it.
If a language has RE, then that language can be expressed through TG.
By Kleene's theorem every RE language has an FA, which is also a TG.
FA1 corresponds to r*, then FA1 must accept _______________ string.
r* always contains Λ, so the FA for r* must accept the null string.
FA1 and FA2 are two FA's representing two languages. Then FA3, which is sum of FA1 and FA2, will accept the strings which are
FA1 + FA2 accepts the union: strings accepted by either machine or both.
FA3 expresses r1r2. Then initial state of FA3 will consist of
Words of r1r2 begin with a word of r1, so FA3 starts at the initial state of FA1.
FA3 expresses r1r2. Then there will be at least one final state of FA3 that consist of final state of FA1 and initial state of FA2.
Final states of FA3 are those containing a final state of FA2, not the FA1-final/FA2-initial combination.
No MCQs match this filter.Is filter mein koi MCQ nahi.
Write the points (parts) of Kleene's theorem.
Kleene's theorem has three parts: (1) If a language can be accepted by an FA, then it can be accepted by a TG. (2) If a language can be accepted by a TG, then it can be expressed by an RE. (3) If a language can be expressed by an RE, then it can be accepted by an FA. Hence FA, TG and RE are equivalent ways of describing regular languages.
Write the differences and common points between NFA & DFA.
Similarities: both have a finite set of states, one initial state, some (maybe none) final states, a finite input alphabet, and both accept exactly the regular languages (every NFA can be converted to an equivalent FA). Differences: in an FA (DFA) every state has exactly one transition for each letter, so each string has exactly one path; in an NFA a state may have more than one transition for the same letter, or none, so a string may have several paths or none, and it is accepted if at least one path ends in a final state.
What is the function of mealy machine?
A Mealy machine reads an input string and prints an output character on each transition, so it translates an input string into an output string of the same length. Such machines are used for computing tasks, e.g. the 1's complementing machine and the incrementing machine, which helps in building a machine that adds binary numbers; they also model sequential circuits.
Explain with example that how in GTG's we directly join the initial state with the final state?
By state elimination (bypass): when states are connected in sequence, an intermediate state is removed and its predecessor is joined to its successor by one edge labelled with the concatenation of the REs on the path (including a loop at the removed state with a star). Example: 1 --r1--> 2 --r2--> 3 with loop r3 at 2 becomes 1 --r1 r3* r2--> 3. Repeating this, and combining parallel edges with +, leaves one edge from the initial to the final state whose label is the RE.
Check the given statements are correct or not, if not then correct it. 1. String in regular language can not be infinite. 2. Concatenation of finite letters from alphabets called sigma. 3. There cannot be more than one FAs for same language.
1. True: every string has finite length; an infinite language has infinitely many strings, but each is finite. 2. False: a concatenation of finitely many letters is a string; Σ (sigma) is the alphabet, the finite set of letters. 3. False: one language can be accepted by many different FAs.
Is there any difference in PALINDROME and reverse of palindrome explain it?
PALINDROME is the language of all strings s over Σ with Rev(s) = s, e.g. aba, abba. Reversing a palindrome gives the same string, so the reverse of each word of PALINDROME is itself, and the reverse of the language PALINDROME is PALINDROME again; there is no difference.
Explain Moore Machine?
A Moore machine is a finite machine with output. It has: a finite set of states q0, q1, q2, ... with q0 the initial state; an input alphabet Σ; an output alphabet Γ; a transition table giving the next state for each state and input letter; and an output table giving the character printed by each state when it is entered. It has no final states. Because the initial state prints before any input is read, an input of length n produces an output of length n + 1.
What are the difference & similarities b/w FA & NFA?
Similarities: both have a finite set of states, one initial state, some (maybe none) final states, a finite input alphabet, and both accept exactly the regular languages (every NFA can be converted to an equivalent FA). Differences: in an FA (DFA) every state has exactly one transition for each letter, so each string has exactly one path; in an NFA a state may have more than one transition for the same letter, or none, so a string may have several paths or none, and it is accepted if at least one path ends in a final state.
How can we show transition table of NFA to FA?
Start from the initial state of the NFA as the initial state of the FA. For each new state and each letter, the next FA state is the set (combination) of all NFA states reachable on that letter; if there is no transition, use an empty (dead) state; if there are several, use a state for their combination. Continue until no new states appear. A combined state is final if it contains a final state of the NFA.
Is Kleene's star & Kleene's closure are different?
No. Kleene star and Kleene closure are two names for the same operation: S* is the set of all strings formed by concatenating any number of strings of S, including Λ.
What is the difference b/w Mealy & Moore machine?
In a Moore machine the output is attached to states: each state prints a character when it is entered, so the initial state prints before any input and the output is one character longer than the input. In a Mealy machine the output is attached to transitions (labels input/output), so the output has the same length as the input. Both have no final states, and for every Moore machine there is an equivalent Mealy machine and vice versa (ignoring the first Moore character).
Read the given statements, answer Yes/No and justify why: (i) Is RE infinite? (ii) An alphabet is concatenation of letters and is also called sigma? (iii) All FAs are also NFA or not?
(i) No: an RE is a finite expression; its language may be finite (e.g. aa + b) or infinite (e.g. a*). (ii) No: a concatenation of letters is a string; the alphabet Σ (sigma) is the finite set of letters. (iii) Yes: every FA can be considered an NFA (one with exactly one transition per letter), but not every NFA is an FA.
Any other way to represent the final (+) and initial (-) states?
Yes. The initial state can be shown by an arrow head pointing to it, and a final state by a double circle.
A regular language L has only words ending with "01". Are "1101" and "111011" distinguishable? Justify why.
1101 ends in 01, so it is in L, while 111011 ends in 11, so it is not in L. Taking z = Λ, exactly one of 1101z and 111011z is in L, so the two strings are distinguishable with respect to L.
Can we represent start and final state with + and - sign and is there any other way to represent it?
Yes: the initial (start) state is marked - and a final state +. Alternatively an arrow head can point to the initial state and a final state can be drawn as a double circle.
The language can express in FA then why we need NFA. Justify your answer.
NFAs do not accept more languages than FAs, since every NFA can be converted to an equivalent FA. They are needed for convenience: an NFA for a language is often much smaller and easier to design, and NFAs make the proofs of Kleene's theorem (union, concatenation and closure of FAs) simple, after which the NFA can be converted to an FA.
Make a RE for a language that does not have triple b (bbb) at any place.
(Λ + b + bb)(a + ab + abb)*. Every run of b's has length at most two: at most two b's at the start, and after each a at most two b's.
What does an automaton mean?
An automaton is a machine (model) that works automatically: it reads input and changes state by fixed rules without human help.
Explain Nondeterminism?
Nondeterminism means the next move is not uniquely fixed: from a state there may be several transitions for the same input (or Λ), or none, so a string may have more than one path or no path. TGs, GTGs and NFAs are nondeterministic; a string is accepted if at least one path ends in a final state.
Finite automata with output?
These are FAs that produce an output string for each input string instead of accepting or rejecting it. They have no final states. There are two types: the Moore machine (output attached to states, output length n + 1) and the Mealy machine (output attached to transitions, output length n).
Explain Equivalent?
Two REs are equivalent if they define the same language, e.g. (a + b)*(aa + bb) = (a + b)*aa + (a + b)*bb. Two FAs (or TGs) are equivalent if they accept the same language. Two machines with output are equivalent if they give the same output for every input.
FA doesn't accept strings in which 3 conditions, write all.
An FA accepts no string when: (1) it has no final state; (2) its final states cannot be reached from the initial state (the machine is disconnected); (3) there is no path from the initial state to any final state for any input (for example, no initial state is given).
Define Mealy Machine
A Mealy machine is a finite machine with output in which the output is attached to the transitions. It has: a finite set of states with one initial state; an input alphabet Σ; an output alphabet Γ; and transitions labelled input/output, each showing the next state and the character printed when that letter is read. It has no final states. An input of length n produces an output of length n. Examples are the 1's complementing machine and the incrementing machine.
Write at least one similarity and one difference between DFA & NFA
Similarities: both have a finite set of states, one initial state, some (maybe none) final states, a finite input alphabet, and both accept exactly the regular languages (every NFA can be converted to an equivalent FA). Differences: in an FA (DFA) every state has exactly one transition for each letter, so each string has exactly one path; in an NFA a state may have more than one transition for the same letter, or none, so a string may have several paths or none, and it is accepted if at least one path ends in a final state.
By looking at transition diagram, how can we identify whether it is FA or TG
It is an FA if there is exactly one initial state, every edge is labelled by a single letter, and every state has exactly one outgoing edge for each letter. If some state lacks an edge for a letter or has several, if edges are labelled by strings or Λ, or if there are several start states, it is a TG.
Differentiate FA, TG & GTG
FA: one initial state, edges labelled by single letters, exactly one transition for each letter from every state (deterministic). TG: one or more initial states, edges labelled by strings of letters or Λ, and a state may have several or no edges for an input, so a string may have many paths or none. GTG: like a TG but edges are labelled by regular expressions. All three accept exactly the regular languages.
Different between word and strings?
A string is any concatenation of a finite number of letters from the alphabet Σ (including the null string Λ). A word is a string that belongs to a particular language. So every word is a string, but a string is a word only if it is in the language.
Different between Distinguishable strings and indistinguishable strings?
For a language L over Σ, strings x and y are distinguishable if there is a string z in Σ* such that exactly one of xz and yz is in L. They are indistinguishable if for every z in Σ*, either both xz and yz are in L or both are not.
Explain Mealy machine?
A Mealy machine is a finite machine with output in which the output is attached to the transitions. It has: a finite set of states with one initial state; an input alphabet Σ; an output alphabet Γ; and transitions labelled input/output, each showing the next state and the character printed when that letter is read. It has no final states. An input of length n produces an output of length n. Examples are the 1's complementing machine and the incrementing machine.
Names of four types of automata.
Finite automaton (deterministic FA or NFA), pushdown automaton (PDA), linear bounded automaton (LBA) and Turing machine (TM); finite automata with output (Moore and Mealy machines) are also studied.
Is the following statement true? A regular language can not be infinite.
False. A regular language can be infinite, e.g. a* or (a + b)*; every finite language is also regular.
Can you say that for a certain string there may be more than one paths in a TG?
Yes. A TG is nondeterministic, so a string may have more than one path (or none); it is accepted if at least one path ends in a final state.
If a language can be accepted by an FA then it can be accepted by a TG as well. What are the other two statements of Kleene's theorem?
If a language can be accepted by a TG, then it can be expressed by an RE. If a language can be expressed by an RE, then it can be accepted by an FA.
Describe the method of NFA corresponding to Concatenation of FAs.
To build an NFA for FA1FA2: keep both FAs; for each final state of FA1 and each letter, add a transition to the state of FA2 that the initial state of FA2 goes to on that letter. Remove the + sign from the final states of FA1 (unless FA2 accepts Λ) and the - sign from the initial state of FA2. The added edges create nondeterminism at the old final states of FA1, and the result is an NFA accepting the concatenation.
How can we say that two REs are equal?
Two REs are equal (equivalent) if they define the same language, e.g. (a + b)* and (a*b*)*.
What is meant by Kleene star closure of a language?
For a language (or set of strings) S, the Kleene star closure S* is the set of all strings formed by concatenating any finite number of strings of S, including the null string Λ. For an alphabet Σ, Σ* is the set of all strings over Σ.
What the Pumping lemma II says about length(x) + length(y) must be:
For an infinite language accepted by an FA with N states, every word w with length greater than N can be written as w = xyz with y non-null and length(x) + length(y) ≤ N (it does not exceed the number of states), such that xy^n z is in the language for all n = 1, 2, 3, ...
Consider the language S*, where S = {ab, ba}. Can any word in this language contain the substrings aaa or bbb? Why or why not?
No. Each factor ab or ba contains one a and one b. Two equal letters can only be next to each other across the boundary of two factors (the last letter of one and the first letter of the next, as in ba·ab or ab·ba), so a run of the same letter has length at most 2. Hence aaa and bbb never occur.
What is meant by a "language" in automata?
A language is a set of strings (words) over an alphabet Σ, i.e. a subset of Σ*. The set of all words accepted by an automaton is the language recognized by that automaton.
Give the regular expression for EVEN-EVEN language?
(aa + bb + (ab + ba)(aa + bb)*(ab + ba))*
Give an example of a set S such that S* only contains all possible strings of a's and b's that have length divisible by 3
S = {aaa, aab, aba, abb, baa, bab, bba, bbb}, all 8 strings of length 3. Every word of S* is a sequence of such blocks, so its length is a multiple of 3, and every string over {a, b} with length divisible by 3 splits into these blocks.
What is meant by tokenizing a string?
Tokenizing is breaking a string into the letters of the alphabet Σ it is made of, e.g. over Σ = {a, bb} the string abba is tokenized as a, bb, a.
In transition diagram of an FA, how can we represent initial and final states?
The initial state is marked with a minus sign (-) or an arrow pointing to it; a final state is marked with a plus sign (+) or drawn as a double circle.
What the Kleene's Theorem Part I says?
If a language can be accepted by an FA, then it can be accepted by a TG as well.
Show that there are exactly 5832 different finite automata with three states x, y, z over the alphabet {a, b}, where x is always the start state.
Each of the 3 states has one transition for a and one for b, and each transition can go to any of the 3 states: 3^6 = 729 ways. Any subset of the 3 states can be final: 2^3 = 8 ways. The start state is fixed as x. Total = 729 × 8 = 5832.
For proving Kleene's theorem part-II: "If there are more than one transition edges between two states then we can reduce all these transition edges with a single transition edge". Explain this statement with the help of an example.
In a TG (or GTG), if there are several edges from state x to state y labelled r1, r2, ..., rk, they can be replaced by one edge from x to y labelled r1 + r2 + ... + rk, because a path may use any one of them. The same applies to several loops at one state. Example: edges a, b and aa from state 1 to state 2 become one edge labelled (a + b + aa); loops a and bb at state 3 become one loop labelled (a + bb). This step is used in Kleene's theorem part II while reducing a TG to a single edge from start to final state.
Nondeterministic finite automaton (NFA)
An NFA consists of: a finite set of states with one initial state and some final states; an input alphabet Σ; and a finite set of transitions labelled with letters, where a state may have more than one transition for the same letter or none for some letters. A string is accepted if at least one path for it ends in a final state. Every FA is an NFA, and every NFA can be converted to an equivalent FA, so NFAs accept exactly the regular languages.
NFA corresponding to the Closure of an FA
Introduce a new initial state that is also final (so Λ is accepted), with the same outgoing transitions as the old initial state, and remove the - sign of the old initial state. Then, at each final state, add for each letter a transition to the state that the old initial state goes to on that letter. These extra edges create nondeterminism, and the resulting NFA accepts the closure (FA)*. Making the old initial state final instead would wrongly accept extra strings, which is why a new state is used.
Draw TGs: accepting all strings, accepting none, starting with b, not ending in b, containing aa, containing aa or bb
Over {a, b}: all strings: one state that is both initial and final with a loop a, b. None: an initial state with a loop a, b and no final state. Starting with b: initial state 1 --b--> final state 2 with loop a, b at 2. Not ending in b: start state 1 with loop a, b and an edge a from 1 to final state 2, plus a second start state that is also final (to accept Λ). Containing aa: 1 (loop a, b) --aa--> 2+ (loop a, b). Containing aa or bb: 1 (loop a, b) with edges aa and bb to final state 2 (loop a, b).
Let L be any language. Let us define the transpose of L to be the language of exactly those words that are the words in L spelled backward. If w ∈ L then reverse(w) ∈ transpose(L). For example, if L = {a, abb, bbaab, bbbaa} then Transpose(L) = {a, bba, baabb, aabbb}. Prove that if there is an FA that accepts L, then there is a TG that accepts the transpose of L.
Let F be an FA accepting L. Build a TG T: reverse the direction of every edge of F (keeping its label), make every final state of F a start state of T (a TG may have several start states), and make the old start state of F the only final state of T. If w = x1x2...xn is accepted by F, its path goes from the start state to a final state; the same edges reversed give a path in T from that final (now start) state to the old start (now final) state reading xn...x1 = reverse(w). Conversely, any accepting path in T reversed is an accepting path of F for the reversed word. Hence T accepts exactly transpose(L). (If Λ ∈ L the old start state is also a start state of T, so Λ is accepted.)
What is meant by nondeterminism? Draw the TG for the following RE (aa)*b(b*+((aa)+b)*)bb.
Nondeterminism means that, for some string, the machine may have more than one possible path (or none), so the next move is not uniquely determined; TGs, GTGs and NFAs are nondeterministic. For (aa)*b(b* + (aa + b)*)bb, note b* is contained in (aa + b)*, so the RE equals (aa)*b(aa + b)*bb. A TG: start state 1 with a loop labelled aa; an edge labelled b from 1 to state 2; at state 2 loops labelled aa and b; an edge labelled bb from 2 to final state 3.
Construct a regular expression defining the following language over the alphabet Σ = {a,b}: All words that contain at least one of the strings s1, s2, s3 or s4
(a + b)*(s1 + s2 + s3 + s4)(a + b)*
(i) When asked to give a recursive definition for the language PALINDROME over the alphabet Σ = {a, b}, a student wrote: Rule 1: a and b are in PALINDROME. Rule 2: If x is in PALINDROME, then so are axa and bxb. Unfortunately all the words in the language defined above have an odd length and so it is not all of PALINDROME. Fix this problem. (ii) Give a recursive definition for the language EVENPALINDROME of all palindromes of even length.
(i) Change Rule 1 to: Λ, a and b are in PALINDROME (keep Rule 2). Starting from Λ, Rule 2 gives the even palindromes aa, bb, abba, ..., so all palindromes are produced. (ii) Rule 1: Λ is in EVENPALINDROME. Rule 2: If x is in EVENPALINDROME, then so are axa and bxb. No other strings are in EVENPALINDROME.
(i) Let S = {ab, bb} and let T = {ab, bb, bbbb}. Show that S* = T*. (ii) Let S = {ab, bb} and let T = {ab, bb, bbb}. Show that S* ≠ T*. (iii) What principle does this illustrate?
(i) S ⊆ T, so S* ⊆ T*. The only word of T not in S is bbbb = (bb)(bb), which is in S*; so T ⊆ S* and therefore T* ⊆ S*. Hence S* = T*. (ii) bbb is in T* (it is in T). It is not in S*: a word of S* starting with b must start with bb, and the remaining b cannot be formed from ab or bb. So S* ≠ T* (though S* ⊆ T*). (iii) Adding to S words that can already be formed from S does not change S*; in general S* = T* exactly when S ⊆ T* and T ⊆ S*.