Xpert
02-19-2011, 11:45 PM
It's the mega file which include all most all the mcq's, quiz and short question with subjective long questions and their answer's So please find the attachment for this.
Q No 1.Give a example of converting a CFG to CNF?
Consider the CFG given below
S→ ABC
A→ aa | b
B→ c
C→d
Its CNF will be
S→ DC
D → AB
A→ EE | b
E→a
B→c
C→d
Q No 2.In the lecture 41 's example, we have converted PDA to conversion form and a
word 'aaaabb' is derived from this conversion form PDA. What are the derivation
steps.
The PDA converted to conversion form has some specific features that are important to
understand first. These features are
The states named START, READ, HERE and ACCEPT are called joints of the machine.
With the help of the conversion form we have been able to achieve that POP state has only
one path out of it and the path taking (multiple paths) decisions take place only on the READ
state.
The word 'aaaabb' is generated as follows from the PDA
START-POP4-PUSH $
This step pops $ and then pushes it to ensure that stack contains $ at the beginning.
READ1-POP6-PUSH $-PUSH a
As first time after reading "a" there is $ at the top of stack so we will follow path segment
READ1-POP6-PUSH $-PUSH a
READ1-POP5-PUSH a-PUSH a
Now a is on the top of the stack so we will follow READ1-POP5-PUSH a-PUSH a
READ1-POP5-PUSH a-PUSH a
Again following same segment for a
READ1-POP5-PUSH a-PUSH a
Again following same segment for a
READ1-POP1- HERE-POP2
As we read b on input tape.
READ2-POP1-HERE-POP2
As we read b on input tape.
READ2-POP3-ACCEPT.
As we read Δ from the input tape
Q No 3.How to differentiate between "wanted" and "unwanted branch" ?
When we derive a word in Top down parsing beginning with the starting Non Terminal the
branches of the tree that do not lead to our required word are left aside these branches are
called unwanted branches.
For example for CFG
S----->AA
A----->a | b
If we want to generate the word "aa" we will leave the branch generated by the production A-
----->b.
Q No 4.What is the difference between intersection and union of a language?
Intersection of two languages will consist of all those words which are in both languages
while union of two languages will consist of all those words which are present in at least one
language.
Symbol for intersection is ∩ and for union is U.
Q No 5.What is the difference between Context free languages and regular
languages?
Regular languages can be represented by FA‟s because we do not need any memory to
recognize (accept or reject them on FA) them but there is another class of languages that can
not be represented by FA‟s because these languages require that we have some memory (with
the help of memory we can store letters of the string we are checking so that we can compare
them with next coming letters in the string).
For example language anbn requires that we must store a‟s and then compare their count with
next coming b‟s so that we can check whether a‟s are equal to b‟s or not.
Due to this reason we use Context Free Grammars to represent them because we can5t write
RE‟s for them.
So Context Free Languages represent a broader category this category also include regular
languages as subcategory. It means that context free languages include regular languages as
well as some other languages.
Q No 6.What is the difference between Moore and Mealey machines?
In Mealy Machine we read input string letters and generate output while moving along
the paths from one state to another while in Moore machine we generate output on
reaching the state so the output pattern of Moore machine contains one extra letter
because we generated output for state q0 where we read nothing.
Q No 7.What does the following terms mean
i. STACK Consistent
ii. Y-able Paths
iii. Working string
iv. Semi Word means
Stack consistence means that in the PDA converted in the conversion form, when we
follow a path segment (which is formed by combining start, read or here state with
next read, here or accept state on the path) along the PDA its pop state should have
the path for the same letter that is present on the top of the stack at that stage. If this
doesn‟t happen our PDA will crash because in conversion form of the PDA the pop
state has only one letter path, so if we could not be able to find that letter on the top of
the stack our PDA will crash (if will not find path where to go from that state)
Working string means the string present on the input tape.
Y-able Paths means that when we follow a certain sequence of rows from the row
table to generate a path for a word form start state to accept state. The path (sequence
of rows) should be stack as well as joint consistent it means that rows should end at
the same read or here state (join consistency ) and the rows should be able to pop the
letter from the top that is indicated in the pop state of the row.
Semi word is the string of terminals it may be null string ending with a Non terminals
on the right.
For example some semi words are
aaS
aabbA
B
Question: Is Automata Theory is a Programming Subject or theoretical?
Answer:
Automata theory is the study of abstract computing devices, or "machines". This
topic goes back to the days before digital computers and describes what is
possible to compute using an abstract machine.
These ideas directly apply to creating compilers, programming languages, and
designing applications. They also provide a formal framework to analyze new
types of computing devices, e.g. biocomputers or quantum computers
Question: What are practical Examples of the implications of Automata Theory
and the formal Languages?
Answer:
Grammars and languages are closely related to automata theory and
are the basis of many important software components like:
– Compilers and interpreters
– Text editors and processors
– Text searching
– System verification
Question: What are the Types of Automata?
Answer: The Types of Automata Theory are
1. Finite Automata
2. Regular Languages
3. Linear-bounded Automata
4. Context Sensitive Languages
5. Push-Down Automata
6. Context Free Languages
7. Turing Machines
8. Recursively innumerable languages
There are others as well like,
Random Access Machines
Parallel Random Access Machines
Arrays of Automata
Question: How types of Automata Differ?
Answer: They differ in the following areas
1. Complexity (or Simplicity)
2. Power
3. In the function that can be computed.
4. In the languages that can be accepted.
Question: What is the difference between the alphabet and an element of a set?
Answer:
Alphabets is a set of letters nothing else but a set of strings (elements) can have
more than one letters in one string.
Question: Difference between Palindrome and Reverse function?
Answer: The language consisting of Λ and the strings s defined over Σ such that Rev(s)=s.
It is to be denoted that the words of PALINDROME are called palindromes.
Reverse (w) = w
Example: Σ={a,b},
PALINDROME={Λ , a, b, aa, bb, aaa, aba, bab, bbb, ...}
If a is a word in some language L, then reverse (a) is the same string of letters spelled backwards,
called the reverse of a.
e.g
reverse (xxx) = xxx
reverse (623) = 326
reverse (140) = 041
Question: Define Strings?
Answer: Concatenation of finite letters from the alphabet is called a string.
e.g If Σ= {a,b} then a language L can be defined as
L = {a, abab, aaabb, ababababababababab,...............}
it's mean all words with a's more or equal to b's
Question: Define empty or null strings?
Answer: Concatenation of finite letters from the alphabet is called a string.
Sometimes a string with no symbol at all is used, denoted by (Small Greek letter Lambda) λ
or (Capital Greek letter Lambda) Λ, is called an empty string or null string.
Question: Difference between string and word?
Answer: Any combination of letters of alphabet that follows rules of language is called a word.
A string is a finite sequence of symbols from an alphabet.
Question: There are as many palindromes of length 2n as there are of length 2n-1, please explain?
Answer: If we try to create palindromes then middle elements (2 in even palindromes & 1 in odd
palindrome) does not cause any change in no. of palindromes
Defining the language PALINDROME, of length 2n and 2n-1 defined over S = {a,b}
e.g if we take n= 2 for 2n
Length (2n) = 4 and string can be written as
{aaaa, abba, baab, bbbb}
And if we take n = 2 for 2n-1
Length (2n-1) = 3 and string can be written as
{aaa, aba, bab, bbb}
Question: Define Kleene Star?
Answer: Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ*, is the collection of
all strings defined over Σ, including Λ.
It is to be noted that Kleene Star Closure can be defined over any set of strings.
Examples
If Σ = {x}
Then Σ* = {Λ, x, xx, xxx, xxxx, ….}
If Σ = {0,1}
Then Σ* = {Λ, 0, 1, 00, 01, 10, 11, ….}
If Σ = {aaB, c}
Then Σ* = {Λ, aaB, c, aaBaaB, aaBc, caaB, cc, ….}
Note:
Languages generated by Kleene Star Closure of set of strings, are infinite languages. (By
infinite language, it is supposed that the language contains infinite many words, each of finite
length).
Question: Why do not we can write" ba" in the set of PALINDROME while it is reverse of
"ab".
Answer: The language consisting of Λ and the strings s defined over Σ such that Rev(s)=s.
It is to be denoted that the words of PALINDROME are called palindromes.
Example
For Σ={a,b},
PALINDROME={Λ , a, b, aa, bb, aaa, aba, bab, bbb, ...}
All two length string cannot satisfied the palindrome. aa and bb in palindrome but
ba and ab are not in palindrome.
Question: What are the steps of Recursive Definition of Languages?
Answer: A recursive definition is characteristically a three-step process.
First, we specify some basic objects in the set.
Second, we give rules for constructing more objects in the set from ones we already know.
Third, we declare that no objects except those constructed in this way are allowed in the set.
Question: Strings that ending in "a " and strings containing exactly one "a".
Answer: Its means all string ending in a
e.g Σ= {a, b}
{a, aa, ba, aba, baa,…….}
Exactly a, defined over Σ= {a, b}
{ab, ba, abb, bba,……... }
Question: What is Lexical Analyzer?
Answer: The first phase of the compiler is the lexical analyzer, also known as the scanner, which
recognizes the basic language units, called tokens.
• The exact characters in a token is called its lexeme.
• Tokens are classified by token types, e.g. identifiers, constant literals, strings,
operators, punctuation marks, and key words.
• Different types of tokens may have their own semantic attributes (or values) which
must be extracted and stored in the symbol table.
• The lexical analyzer may perform semantic actions to extract such values and insert
them in the symbol table.
Question: What is accepting string language?
Answer: The strings which follow rules for the language are accepted in language.
• Let u and v be strings. Then uv denotes the string obtained by concatenating u with
v, that is, uv is the string obtained by appending the sequence of symbols of v to that
of u. For example if u = aab and v = bbab,
then uv = aabbbab. Note that vu = bbabaab uv. We are going to use first few
symbols of English alphabet such as a and b to denote symbols of an alphabet and
those toward the end such as u and v for strings.
Question: What is transition table?
Answer: A complete transition table contains one column for each character. To save space,
table compression may be used. Only non-error entries are explicitly represented in
the table, using hashing, indirection or linked structures.
Tabular representation of a function that takes two arguments and returns a value
0 1
Q No 1.Give a example of converting a CFG to CNF?
Consider the CFG given below
S→ ABC
A→ aa | b
B→ c
C→d
Its CNF will be
S→ DC
D → AB
A→ EE | b
E→a
B→c
C→d
Q No 2.In the lecture 41 's example, we have converted PDA to conversion form and a
word 'aaaabb' is derived from this conversion form PDA. What are the derivation
steps.
The PDA converted to conversion form has some specific features that are important to
understand first. These features are
The states named START, READ, HERE and ACCEPT are called joints of the machine.
With the help of the conversion form we have been able to achieve that POP state has only
one path out of it and the path taking (multiple paths) decisions take place only on the READ
state.
The word 'aaaabb' is generated as follows from the PDA
START-POP4-PUSH $
This step pops $ and then pushes it to ensure that stack contains $ at the beginning.
READ1-POP6-PUSH $-PUSH a
As first time after reading "a" there is $ at the top of stack so we will follow path segment
READ1-POP6-PUSH $-PUSH a
READ1-POP5-PUSH a-PUSH a
Now a is on the top of the stack so we will follow READ1-POP5-PUSH a-PUSH a
READ1-POP5-PUSH a-PUSH a
Again following same segment for a
READ1-POP5-PUSH a-PUSH a
Again following same segment for a
READ1-POP1- HERE-POP2
As we read b on input tape.
READ2-POP1-HERE-POP2
As we read b on input tape.
READ2-POP3-ACCEPT.
As we read Δ from the input tape
Q No 3.How to differentiate between "wanted" and "unwanted branch" ?
When we derive a word in Top down parsing beginning with the starting Non Terminal the
branches of the tree that do not lead to our required word are left aside these branches are
called unwanted branches.
For example for CFG
S----->AA
A----->a | b
If we want to generate the word "aa" we will leave the branch generated by the production A-
----->b.
Q No 4.What is the difference between intersection and union of a language?
Intersection of two languages will consist of all those words which are in both languages
while union of two languages will consist of all those words which are present in at least one
language.
Symbol for intersection is ∩ and for union is U.
Q No 5.What is the difference between Context free languages and regular
languages?
Regular languages can be represented by FA‟s because we do not need any memory to
recognize (accept or reject them on FA) them but there is another class of languages that can
not be represented by FA‟s because these languages require that we have some memory (with
the help of memory we can store letters of the string we are checking so that we can compare
them with next coming letters in the string).
For example language anbn requires that we must store a‟s and then compare their count with
next coming b‟s so that we can check whether a‟s are equal to b‟s or not.
Due to this reason we use Context Free Grammars to represent them because we can5t write
RE‟s for them.
So Context Free Languages represent a broader category this category also include regular
languages as subcategory. It means that context free languages include regular languages as
well as some other languages.
Q No 6.What is the difference between Moore and Mealey machines?
In Mealy Machine we read input string letters and generate output while moving along
the paths from one state to another while in Moore machine we generate output on
reaching the state so the output pattern of Moore machine contains one extra letter
because we generated output for state q0 where we read nothing.
Q No 7.What does the following terms mean
i. STACK Consistent
ii. Y-able Paths
iii. Working string
iv. Semi Word means
Stack consistence means that in the PDA converted in the conversion form, when we
follow a path segment (which is formed by combining start, read or here state with
next read, here or accept state on the path) along the PDA its pop state should have
the path for the same letter that is present on the top of the stack at that stage. If this
doesn‟t happen our PDA will crash because in conversion form of the PDA the pop
state has only one letter path, so if we could not be able to find that letter on the top of
the stack our PDA will crash (if will not find path where to go from that state)
Working string means the string present on the input tape.
Y-able Paths means that when we follow a certain sequence of rows from the row
table to generate a path for a word form start state to accept state. The path (sequence
of rows) should be stack as well as joint consistent it means that rows should end at
the same read or here state (join consistency ) and the rows should be able to pop the
letter from the top that is indicated in the pop state of the row.
Semi word is the string of terminals it may be null string ending with a Non terminals
on the right.
For example some semi words are
aaS
aabbA
B
Question: Is Automata Theory is a Programming Subject or theoretical?
Answer:
Automata theory is the study of abstract computing devices, or "machines". This
topic goes back to the days before digital computers and describes what is
possible to compute using an abstract machine.
These ideas directly apply to creating compilers, programming languages, and
designing applications. They also provide a formal framework to analyze new
types of computing devices, e.g. biocomputers or quantum computers
Question: What are practical Examples of the implications of Automata Theory
and the formal Languages?
Answer:
Grammars and languages are closely related to automata theory and
are the basis of many important software components like:
– Compilers and interpreters
– Text editors and processors
– Text searching
– System verification
Question: What are the Types of Automata?
Answer: The Types of Automata Theory are
1. Finite Automata
2. Regular Languages
3. Linear-bounded Automata
4. Context Sensitive Languages
5. Push-Down Automata
6. Context Free Languages
7. Turing Machines
8. Recursively innumerable languages
There are others as well like,
Random Access Machines
Parallel Random Access Machines
Arrays of Automata
Question: How types of Automata Differ?
Answer: They differ in the following areas
1. Complexity (or Simplicity)
2. Power
3. In the function that can be computed.
4. In the languages that can be accepted.
Question: What is the difference between the alphabet and an element of a set?
Answer:
Alphabets is a set of letters nothing else but a set of strings (elements) can have
more than one letters in one string.
Question: Difference between Palindrome and Reverse function?
Answer: The language consisting of Λ and the strings s defined over Σ such that Rev(s)=s.
It is to be denoted that the words of PALINDROME are called palindromes.
Reverse (w) = w
Example: Σ={a,b},
PALINDROME={Λ , a, b, aa, bb, aaa, aba, bab, bbb, ...}
If a is a word in some language L, then reverse (a) is the same string of letters spelled backwards,
called the reverse of a.
e.g
reverse (xxx) = xxx
reverse (623) = 326
reverse (140) = 041
Question: Define Strings?
Answer: Concatenation of finite letters from the alphabet is called a string.
e.g If Σ= {a,b} then a language L can be defined as
L = {a, abab, aaabb, ababababababababab,...............}
it's mean all words with a's more or equal to b's
Question: Define empty or null strings?
Answer: Concatenation of finite letters from the alphabet is called a string.
Sometimes a string with no symbol at all is used, denoted by (Small Greek letter Lambda) λ
or (Capital Greek letter Lambda) Λ, is called an empty string or null string.
Question: Difference between string and word?
Answer: Any combination of letters of alphabet that follows rules of language is called a word.
A string is a finite sequence of symbols from an alphabet.
Question: There are as many palindromes of length 2n as there are of length 2n-1, please explain?
Answer: If we try to create palindromes then middle elements (2 in even palindromes & 1 in odd
palindrome) does not cause any change in no. of palindromes
Defining the language PALINDROME, of length 2n and 2n-1 defined over S = {a,b}
e.g if we take n= 2 for 2n
Length (2n) = 4 and string can be written as
{aaaa, abba, baab, bbbb}
And if we take n = 2 for 2n-1
Length (2n-1) = 3 and string can be written as
{aaa, aba, bab, bbb}
Question: Define Kleene Star?
Answer: Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ*, is the collection of
all strings defined over Σ, including Λ.
It is to be noted that Kleene Star Closure can be defined over any set of strings.
Examples
If Σ = {x}
Then Σ* = {Λ, x, xx, xxx, xxxx, ….}
If Σ = {0,1}
Then Σ* = {Λ, 0, 1, 00, 01, 10, 11, ….}
If Σ = {aaB, c}
Then Σ* = {Λ, aaB, c, aaBaaB, aaBc, caaB, cc, ….}
Note:
Languages generated by Kleene Star Closure of set of strings, are infinite languages. (By
infinite language, it is supposed that the language contains infinite many words, each of finite
length).
Question: Why do not we can write" ba" in the set of PALINDROME while it is reverse of
"ab".
Answer: The language consisting of Λ and the strings s defined over Σ such that Rev(s)=s.
It is to be denoted that the words of PALINDROME are called palindromes.
Example
For Σ={a,b},
PALINDROME={Λ , a, b, aa, bb, aaa, aba, bab, bbb, ...}
All two length string cannot satisfied the palindrome. aa and bb in palindrome but
ba and ab are not in palindrome.
Question: What are the steps of Recursive Definition of Languages?
Answer: A recursive definition is characteristically a three-step process.
First, we specify some basic objects in the set.
Second, we give rules for constructing more objects in the set from ones we already know.
Third, we declare that no objects except those constructed in this way are allowed in the set.
Question: Strings that ending in "a " and strings containing exactly one "a".
Answer: Its means all string ending in a
e.g Σ= {a, b}
{a, aa, ba, aba, baa,…….}
Exactly a, defined over Σ= {a, b}
{ab, ba, abb, bba,……... }
Question: What is Lexical Analyzer?
Answer: The first phase of the compiler is the lexical analyzer, also known as the scanner, which
recognizes the basic language units, called tokens.
• The exact characters in a token is called its lexeme.
• Tokens are classified by token types, e.g. identifiers, constant literals, strings,
operators, punctuation marks, and key words.
• Different types of tokens may have their own semantic attributes (or values) which
must be extracted and stored in the symbol table.
• The lexical analyzer may perform semantic actions to extract such values and insert
them in the symbol table.
Question: What is accepting string language?
Answer: The strings which follow rules for the language are accepted in language.
• Let u and v be strings. Then uv denotes the string obtained by concatenating u with
v, that is, uv is the string obtained by appending the sequence of symbols of v to that
of u. For example if u = aab and v = bbab,
then uv = aabbbab. Note that vu = bbabaab uv. We are going to use first few
symbols of English alphabet such as a and b to denote symbols of an alphabet and
those toward the end such as u and v for strings.
Question: What is transition table?
Answer: A complete transition table contains one column for each character. To save space,
table compression may be used. Only non-error entries are explicitly represented in
the table, using hashing, indirection or linked structures.
Tabular representation of a function that takes two arguments and returns a value
0 1