All Exams >
Computer Science Engineering (CSE) >
6 Months Preparation for GATE CSE >
All Questions
All questions of Context Free Grammar, Languages and Pushdown Automata for Computer Science Engineering (CSE) Exam
One of the uses of CNF is to turn parse tree into:- a)AVL trees
- b)Binary search trees
- c)Binary trees
- d)None of the above
Correct answer is option 'C'. Can you explain this answer?
One of the uses of CNF is to turn parse tree into:
a)
AVL trees
b)
Binary search trees
c)
Binary trees
d)
None of the above
|
Crack Gate answered |
CNF (Chomsky’s normal form). A grammar is in the form of CNF is as follows:
S → AB
S → a
Where A, B are non-terminals and a is the terminal.
All productions should be of length 2.
S → AB
S → a
Where A, B are non-terminals and a is the terminal.
All productions should be of length 2.
- In this, first eliminate useless symbols for CNF. Eliminate the null productions and unit productions.
- In CFL it is possible to find atmost two short substrings that we can pump i times for any integer i.
- Pumping Lemma for CFL is used to examine the size of parse trees. One of the uses of CNF is to turn the parse into binary trees.
To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is:- a)2n − 1
- b)2n
- c)n + 1
- d)n2
Correct answer is option 'A'. Can you explain this answer?
To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is:
a)
2n − 1
b)
2n
c)
n + 1
d)
n2
|
Sushant Nambiar answered |
The correct answer is b) 2n-1.
In Chomsky normal form grammar, all productions are of the form A -> BC or A -> a, where A, B, and C are non-terminals and a is a terminal.
To obtain a string of n terminals, we need to use n-1 productions of the form A -> BC and one production of the form A -> a.
Therefore, the total number of productions needed is (n-1) + 1 = n.
In Chomsky normal form grammar, all productions are of the form A -> BC or A -> a, where A, B, and C are non-terminals and a is a terminal.
To obtain a string of n terminals, we need to use n-1 productions of the form A -> BC and one production of the form A -> a.
Therefore, the total number of productions needed is (n-1) + 1 = n.
Let G = (V, T, S, P) be any context-free grammar without any λ-productions or unit productions. Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by:Where |⋅| denotes the cardinality of the set.- a)(K - 1)|P| + |T| -1
- b)(K - 1)|P| + |T|
- c)K |P| + |T| -1
- d)K |P| + |T|
Correct answer is option 'B'. Can you explain this answer?
Let G = (V, T, S, P) be any context-free grammar without any λ-productions or unit productions. Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by:
Where |⋅| denotes the cardinality of the set.
a)
(K - 1)|P| + |T| -1
b)
(K - 1)|P| + |T|
c)
K |P| + |T| -1
d)
K |P| + |T|
|
Megha Yadav answered |
Restrictions on its production rules. Here, V represents the set of variables (non-terminals), T represents the set of terminals, S represents the start symbol, and P represents the set of production rules.
A context-free grammar is a formal grammar in which every production rule has exactly one variable on the left-hand side. This means that the left-hand side of each production rule can be replaced by any sequence of variables and terminals.
The absence of any restrictions on the production rules means that they can be of any form and can have any number of variables and terminals on both sides. However, it is important to note that there are certain conventions and common practices followed in defining and using context-free grammars.
For example, in a context-free grammar, the start symbol S is usually a single variable and the production rules are typically defined in a specific format. Each production rule has a single variable on the left-hand side and a sequence of variables and terminals on the right-hand side. The production rules are used to generate valid strings in the language defined by the grammar.
In summary, a context-free grammar without any restrictions on its production rules can have any form of rules, but it is common to follow certain conventions and practices in order to define and use the grammar effectively.
A context-free grammar is a formal grammar in which every production rule has exactly one variable on the left-hand side. This means that the left-hand side of each production rule can be replaced by any sequence of variables and terminals.
The absence of any restrictions on the production rules means that they can be of any form and can have any number of variables and terminals on both sides. However, it is important to note that there are certain conventions and common practices followed in defining and using context-free grammars.
For example, in a context-free grammar, the start symbol S is usually a single variable and the production rules are typically defined in a specific format. Each production rule has a single variable on the left-hand side and a sequence of variables and terminals on the right-hand side. The production rules are used to generate valid strings in the language defined by the grammar.
In summary, a context-free grammar without any restrictions on its production rules can have any form of rules, but it is common to follow certain conventions and practices in order to define and use the grammar effectively.
The Grammar can be defined as: G=(V, ∑, p, S)In the given definition, what does S represents?- a)Accepting State
- b)Starting Variable
- c)Sensitive Grammar
- d)None of these
Correct answer is option 'B'. Can you explain this answer?
The Grammar can be defined as: G=(V, ∑, p, S)In the given definition, what does S represents?
a)
Accepting State
b)
Starting Variable
c)
Sensitive Grammar
d)
None of these
|
Aditya Nair answered |
G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite productions, S= Starting Variable.
If L(G) is accepted by pushdown automaton and x is a string of length 21 in L(G), how long is a derivative of x in G, if G is Chomsky normal form?- a)40
- b)41
- c)42
- d)39
Correct answer is option 'B'. Can you explain this answer?
If L(G) is accepted by pushdown automaton and x is a string of length 21 in L(G), how long is a derivative of x in G, if G is Chomsky normal form?
a)
40
b)
41
c)
42
d)
39
|
Sudhir Patel answered |
Chomsky normal form
S → AB
A → a
B → b
Length of string = |x|
S → AB
A → a
B → b
Length of string = |x|
Length of the derivate of string x in context free grammar:
2|x| – 1 = 2 × 21 - 1 = 41
2|x| – 1 = 2 × 21 - 1 = 41
Note:
Question say steps needed to generated string of 10 length
e.g. if we need to generate ab (string of length 2)
S → AB
S → aB
S → ab
Number of steps = 2× 2 – 1 = 3
Question say steps needed to generated string of 10 length
e.g. if we need to generate ab (string of length 2)
S → AB
S → aB
S → ab
Number of steps = 2× 2 – 1 = 3
Which of the following grammar is in Greibach Normal Form?
A. S → AB, A → a, B → b
B. S → aA | A → ϵ
C. S → Aa, A → a- a)Only A and B
- b)Only B and C
- c)A, B and C
- d)None of these
Correct answer is option 'D'. Can you explain this answer?
Which of the following grammar is in Greibach Normal Form?
A. S → AB, A → a, B → b
B. S → aA | A → ϵ
C. S → Aa, A → a
A. S → AB, A → a, B → b
B. S → aA | A → ϵ
C. S → Aa, A → a
a)
Only A and B
b)
Only B and C
c)
A, B and C
d)
None of these
|
|
Sudhir Patel answered |
A context grammar is said to be in Greibech Normal Form if all the productions have the form
S → xA
where x ϵ T and x ϵ V*
T is terminal and V is variable (non-terminal)
S → xA
where x ϵ T and x ϵ V*
T is terminal and V is variable (non-terminal)
- Option A: Not in GNF. Since production S → AB is not in GNF
- Option B: Not in GNF. Since production A → ϵ is not in GNF
- Option C: Not in GNF. Since production S → Aa is not in GNF
For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?- a)Non regular language
- b)0^n1^n | n>=0
- c)0^n1^n | n>=1
- d)None of the mentioned
Correct answer is option 'D'. Can you explain this answer?
For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
a)
Non regular language
b)
0^n1^n | n>=0
c)
0^n1^n | n>=1
d)
None of the mentioned
|
Rishika Pillai answered |
L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.
If a Context Free Grammar G is in Chomsky Normal Form, to derive a string of length 101 number of productions needed is _____.
Correct answer is '201'. Can you explain this answer?
If a Context Free Grammar G is in Chomsky Normal Form, to derive a string of length 101 number of productions needed is _____.
|
Gate Gurus answered |
Concepts:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal
Data:
x = 101
n → number of productions required to generates string of length x.
x = 101
n → number of productions required to generates string of length x.
Formula:
n = 2x – 1
n = 2x – 1
where x is the length of the string
Calculation:
n = 2(101) – 1
∴ n = 201
n = 2(101) – 1
∴ n = 201
The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is- a)3
- b)7
- c)5
- d)6
Correct answer is option 'C'. Can you explain this answer?
The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
a)
3
b)
7
c)
5
d)
6
|
Ankit Mehta answered |
The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}
Which of the following allows stacked values to be sub-stacks rather than just finite symbols?- a)Push Down Automaton
- b)Turing Machine
- c)Nested Stack Automaton
- d)None of the mentioned
Correct answer is option 'C'. Can you explain this answer?
Which of the following allows stacked values to be sub-stacks rather than just finite symbols?
a)
Push Down Automaton
b)
Turing Machine
c)
Nested Stack Automaton
d)
None of the mentioned
|
|
Rishika Pillai answered |
In computational theory, a nested stack automaton is a finite automaton which makes use of stack containing data which can be additional stacks.
Which of the following is called Bar-Hillel lemma?- a)Pumping lemma for regular language
- b)Pumping lemma for context free languages
- c)Pumping lemma for context sensitive languages
- d)None of the mentioned
Correct answer is option 'D'. Can you explain this answer?
Which of the following is called Bar-Hillel lemma?
a)
Pumping lemma for regular language
b)
Pumping lemma for context free languages
c)
Pumping lemma for context sensitive languages
d)
None of the mentioned
|
Amrutha Singh answered |
In automata theory, the pumping lemma for context free languages, also kmown as the Bar-Hillel lemma, represents a property of all context free languages.
With reference of a DPDA, which among the following do we perform from the start state with an empty stack?- a)process the whole string
- b)end in final state
- c)end with an empty stack
- d)all of the mentioned
Correct answer is option 'D'. Can you explain this answer?
With reference of a DPDA, which among the following do we perform from the start state with an empty stack?
a)
process the whole string
b)
end in final state
c)
end with an empty stack
d)
all of the mentioned
|
|
Manasa Dey answered |
The empty stack in the end is our requirement relative to finite state automatons.
Finite-state acceptors for the nested words can be:- a)nested word automata
- b)push down automata
- c)ndfa
- d)none of the mentioned
Correct answer is option 'A'. Can you explain this answer?
Finite-state acceptors for the nested words can be:
a)
nested word automata
b)
push down automata
c)
ndfa
d)
none of the mentioned
|
|
Jatin Joshi answered |
The linear encodings of languages accepted by finite nested word automata gives the class of ‘visibly pushdown automata’.
Push down automata accepts _________ languages.- a)Type 3
- b)Type 2
- c)Type 1
- d)Type 0
Correct answer is option 'B'. Can you explain this answer?
Push down automata accepts _________ languages.
a)
Type 3
b)
Type 2
c)
Type 1
d)
Type 0
|
Rohit Mukherjee answered |
Push down automata is for Context free languages and they are termed as Type 2 languages according to Chomsky hierarchy.
The instantaneous PDA is has the following elements- a)State
- b)Unconsumed input
- c)Stack content
- d)All of the mentioned
Correct answer is option 'D'. Can you explain this answer?
The instantaneous PDA is has the following elements
a)
State
b)
Unconsumed input
c)
Stack content
d)
All of the mentioned
|
|
Aman Menon answered |
The instantaneous description of a PDA is represented by 3 tuple:
(q,w,s)
where q is the state, w is the unconsumed input and s is the stack content.
(q,w,s)
where q is the state, w is the unconsumed input and s is the stack content.
Which of the following can be accepted by a DPDA?- a)The set of even length palindrome over {a,b}
- b)The set of odd length palindrome over {a,b}
- c){xxc| where c stands for the complement,{0,1}}
- d)None of the mentioned
Correct answer is option 'D'. Can you explain this answer?
Which of the following can be accepted by a DPDA?
a)
The set of even length palindrome over {a,b}
b)
The set of odd length palindrome over {a,b}
c)
{xxc| where c stands for the complement,{0,1}}
d)
None of the mentioned
|
Tanvi Datta answered |
Theorem: The language pal of palindromes over the alphabet {0,1} cannot be accepted by any finite automaton , and it is therefore not regular.
Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 nad L2 so that ___________is not a CFL.- a)L1∩L2
- b)L1′
- c)L1*
- d)None of the mentioned
Correct answer is option 'C'. Can you explain this answer?
Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 nad L2 so that ___________is not a CFL.
Statement: There are CFLs L1 nad L2 so that ___________is not a CFL.
a)
L1∩L2
b)
L1′
c)
L1*
d)
None of the mentioned
|
|
Rishabh Sharma answered |
A set of context free language is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
a) Union
b) Concatenation
c) Kleene
Which among the following is not a part of the Context free grammar tuple?- a)End symbol
- b)Start symbol
- c)Variable
- d)Production
Correct answer is option 'A'. Can you explain this answer?
Which among the following is not a part of the Context free grammar tuple?
a)
End symbol
b)
Start symbol
c)
Variable
d)
Production
|
Raghav Basu answered |
Explanation:
Context-Free Grammar Tuple:
A context-free grammar (CFG) is defined by a 4-tuple consisting of the following components:
- Set of Variables
- Set of Terminals
- Start Symbol
- Set of Productions
End Symbol:
The "End Symbol" is not a part of the context-free grammar tuple. The concept of an end symbol is not typically used in the formal definition of a CFG. The grammar is defined in terms of variables, terminals, start symbol, and productions, which together determine the language generated by the grammar.
Start Symbol:
The start symbol is a key component of a CFG as it specifies which symbol the derivation process should start from. It is one of the essential elements of the grammar tuple.
Variable:
Variables are symbols that can be replaced by other symbols in the production rules of the grammar. They are used to represent different structures or components of the language being generated.
Production:
Productions define the rules for generating strings in the language. Each production consists of a variable on the left-hand side and a sequence of variables and terminals on the right-hand side.
In a context-free grammar tuple, the end symbol, which is not a standard component, is replaced by the set of terminals, which represent the basic symbols that make up the language.
Context-Free Grammar Tuple:
A context-free grammar (CFG) is defined by a 4-tuple consisting of the following components:
- Set of Variables
- Set of Terminals
- Start Symbol
- Set of Productions
End Symbol:
The "End Symbol" is not a part of the context-free grammar tuple. The concept of an end symbol is not typically used in the formal definition of a CFG. The grammar is defined in terms of variables, terminals, start symbol, and productions, which together determine the language generated by the grammar.
Start Symbol:
The start symbol is a key component of a CFG as it specifies which symbol the derivation process should start from. It is one of the essential elements of the grammar tuple.
Variable:
Variables are symbols that can be replaced by other symbols in the production rules of the grammar. They are used to represent different structures or components of the language being generated.
Production:
Productions define the rules for generating strings in the language. Each production consists of a variable on the left-hand side and a sequence of variables and terminals on the right-hand side.
In a context-free grammar tuple, the end symbol, which is not a standard component, is replaced by the set of terminals, which represent the basic symbols that make up the language.
Let ∑={0,1}* and the grammar G be:
S->ε
S->SS
S->0S1|1S0
State which of the following is true for the given- a)Language of all and only Balanced strings
- b)It contains equal number of 0’s and 1’s
- c)Ambiguous Grammar
- d)All of the mentioned
Correct answer is option 'D'. Can you explain this answer?
Let ∑={0,1}* and the grammar G be:
S->ε
S->SS
S->0S1|1S0
State which of the following is true for the given
S->ε
S->SS
S->0S1|1S0
State which of the following is true for the given
a)
Language of all and only Balanced strings
b)
It contains equal number of 0’s and 1’s
c)
Ambiguous Grammar
d)
All of the mentioned
|
|
Sagar Saha answered |
A string is said to be balanced if it consist of equal number of 0’s and 1’s.
There exists a Context free grammar such that:X->aXWhich among the following is correct with respect to the given assertion?- a)Left Recursive Grammar
- b)Right Recursive Grammar
- c)Non Recursive Grammar
- d)None of the mentioned
Correct answer is option 'B'. Can you explain this answer?
There exists a Context free grammar such that:X->aXWhich among the following is correct with respect to the given assertion?
a)
Left Recursive Grammar
b)
Right Recursive Grammar
c)
Non Recursive Grammar
d)
None of the mentioned
|
|
Shounak Sharma answered |
The grammar with right recursive production is known as Right recursive grammar. Right recursive production is of the form X->aX where a is a terminal and X is a non terminal.
Which of the following strings is not generated by the given grammar:S->SaSbS|e- a)aabb
- b)abab
- c)abaabb
- d)None of the mentioned
Correct answer is option 'D'. Can you explain this answer?
Which of the following strings is not generated by the given grammar:S->SaSbS|e
a)
aabb
b)
abab
c)
abaabb
d)
None of the mentioned
|
Megha Dasgupta answered |
All the given options are generated by the given grammar. Using the methods of left and right derivations, it is simpler to look for string which a grammar can generate.
A non deterministic two way, nested stack automaton has n-tuple definition. State the value of n.- a)5
- b)8
- c)4
- d)10
Correct answer is option 'D'. Can you explain this answer?
A non deterministic two way, nested stack automaton has n-tuple definition. State the value of n.
a)
5
b)
8
c)
4
d)
10
|
Navya Choudhary answered |
Explanation:
A non-deterministic two-way nested stack automaton is a theoretical model of computation that consists of a finite set of states, an input tape, and two stacks. The automaton can read and write symbols on the input tape and perform stack operations on the two stacks.
The n-tuple definition of a non-deterministic two-way nested stack automaton refers to the number of components or elements in the tuple that represents the configuration of the automaton. Each component of the tuple represents the state of the automaton, the contents of the input tape, and the contents of the two stacks.
To understand why the answer is option 'D' (10), let's break down the components of the n-tuple:
1. State of the automaton: The automaton can be in one of a finite number of states. Let's say there are k states. This contributes k components to the n-tuple.
2. Contents of the input tape: The input tape can contain symbols from a finite alphabet. Let's say the alphabet has m symbols. This contributes m components to the n-tuple.
3. Contents of the two stacks: Each stack can contain symbols from a finite alphabet. Let's say the alphabet has p symbols. This contributes 2p components to the n-tuple, as there are two stacks.
Therefore, the total number of components in the n-tuple is k + m + 2p.
Since the options given are a) 5, b) 8, c) 4, and d) 10, we need to find values for k, m, and p that satisfy the equation k + m + 2p = 10.
One possible combination could be k = 3, m = 2, and p = 2. This gives us 3 + 2 + 2(2) = 10.
Hence, the correct answer is option 'D' (10), as it is possible to have a non-deterministic two-way nested stack automaton with an n-tuple definition consisting of 10 components.
A non-deterministic two-way nested stack automaton is a theoretical model of computation that consists of a finite set of states, an input tape, and two stacks. The automaton can read and write symbols on the input tape and perform stack operations on the two stacks.
The n-tuple definition of a non-deterministic two-way nested stack automaton refers to the number of components or elements in the tuple that represents the configuration of the automaton. Each component of the tuple represents the state of the automaton, the contents of the input tape, and the contents of the two stacks.
To understand why the answer is option 'D' (10), let's break down the components of the n-tuple:
1. State of the automaton: The automaton can be in one of a finite number of states. Let's say there are k states. This contributes k components to the n-tuple.
2. Contents of the input tape: The input tape can contain symbols from a finite alphabet. Let's say the alphabet has m symbols. This contributes m components to the n-tuple.
3. Contents of the two stacks: Each stack can contain symbols from a finite alphabet. Let's say the alphabet has p symbols. This contributes 2p components to the n-tuple, as there are two stacks.
Therefore, the total number of components in the n-tuple is k + m + 2p.
Since the options given are a) 5, b) 8, c) 4, and d) 10, we need to find values for k, m, and p that satisfy the equation k + m + 2p = 10.
One possible combination could be k = 3, m = 2, and p = 2. This gives us 3 + 2 + 2(2) = 10.
Hence, the correct answer is option 'D' (10), as it is possible to have a non-deterministic two-way nested stack automaton with an n-tuple definition consisting of 10 components.
Production Rule: aAb->agb belongs to which of the following category?- a)Regular Language
- b)Context free Language
- c)Context Sensitive Language
- d)Recursively Ennumerable Language
Correct answer is option 'C'. Can you explain this answer?
Production Rule: aAb->agb belongs to which of the following category?
a)
Regular Language
b)
Context free Language
c)
Context Sensitive Language
d)
Recursively Ennumerable Language
|
Abhijeet Mehta answered |
Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has the production rule where the production is context dependent i.e. aAb->agb.
Let G=(V, T, P, S)
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?- a)aabbaab
- b)aabbaa
- c)baabab
- d)None of the mentioned
Correct answer is option 'B'. Can you explain this answer?
Let G=(V, T, P, S)
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?
a)
aabbaab
b)
aabbaa
c)
baabab
d)
None of the mentioned
|
|
Yashvi Das answered |
he step wise grammar translation can be written as:
aAS->aSbaA->aabAS->aabbaa
aAS->aSbaA->aabAS->aabbaa
Which of the following gives a positive result to the pumping lemma restrictions and requirements?- a){aibici|i>=0}
- b){0i1i|i>=0}
- c){ss|s∈{a,b}*}
- d)None of the mentioned
Correct answer is option 'B'. Can you explain this answer?
Which of the following gives a positive result to the pumping lemma restrictions and requirements?
a)
{aibici|i>=0}
b)
{0i1i|i>=0}
c)
{ss|s∈{a,b}*}
d)
None of the mentioned
|
Nandini Mehta answered |
Unfortunately, there is a typo in the question and the word after "i" is missing. Please provide the complete regular expression so that I can answer your question accurately.
What is the pumping length of string of length x?- a)x+1
- b)x
- c)x-1
- d)x2
Correct answer is option 'A'. Can you explain this answer?
What is the pumping length of string of length x?
a)
x+1
b)
x
c)
x-1
d)
x2
|
|
Rishabh Sharma answered |
There exists a property of all strings in the language that are of length p, where p is the constant-called the pumping length .For a finite language L, p is equal to the maximum string length in L plus 1.
If two sets, R and T has no elements in common i.e. RÇT=Æ, then the sets are called- a)Complement
- b)Union
- c)Disjoint
- d)Connected
Correct answer is option 'C'. Can you explain this answer?
If two sets, R and T has no elements in common i.e. RÇT=Æ, then the sets are called
a)
Complement
b)
Union
c)
Disjoint
d)
Connected
|
|
Raghav Basu answered |
Disjoint Sets Explanation:
Disjoint sets are sets that have no elements in common, which means the intersection of the two sets is an empty set. In other words, if two sets R and T are disjoint, then R ∩ T = Ø.
Characteristics of Disjoint Sets:
- Disjoint sets do not share any elements.
- The intersection of disjoint sets is always an empty set.
- Disjoint sets are also called mutually exclusive sets.
Example:
- Let's consider two sets R = {1, 2, 3} and T = {4, 5, 6}. These sets are disjoint because they have no elements in common, and their intersection is an empty set, i.e., R ∩ T = Ø.
Usage:
- Disjoint sets are commonly used in mathematics, statistics, computer science, and various other fields where the absence of shared elements is important for analysis or calculations.
Conclusion:
Understanding and identifying disjoint sets is crucial in various mathematical and computational applications as it helps in determining relationships between different sets and simplifies operations involving set theory.
Disjoint sets are sets that have no elements in common, which means the intersection of the two sets is an empty set. In other words, if two sets R and T are disjoint, then R ∩ T = Ø.
Characteristics of Disjoint Sets:
- Disjoint sets do not share any elements.
- The intersection of disjoint sets is always an empty set.
- Disjoint sets are also called mutually exclusive sets.
Example:
- Let's consider two sets R = {1, 2, 3} and T = {4, 5, 6}. These sets are disjoint because they have no elements in common, and their intersection is an empty set, i.e., R ∩ T = Ø.
Usage:
- Disjoint sets are commonly used in mathematics, statistics, computer science, and various other fields where the absence of shared elements is important for analysis or calculations.
Conclusion:
Understanding and identifying disjoint sets is crucial in various mathematical and computational applications as it helps in determining relationships between different sets and simplifies operations involving set theory.
A null production can be referred to as:- a)String
- b)Symbol
- c)Word
- d)All of the mentioned
Correct answer is option 'A'. Can you explain this answer?
A null production can be referred to as:
a)
String
b)
Symbol
c)
Word
d)
All of the mentioned
|
|
Rohit Mukherjee answered |
Null production is always taken as a string in computational theory.
A CFG for a program describing strings of letters with the word “main” somewhere in the string:- a)-> m a i n
-> | epsilon
-> A | B | … | Z | a | b … | z - b)> m a i n
–>
–> A | B | … | Z | a | b … | z - c)–> m a i n
–> | epsilon
–> A | B | … | Z | a | b … | z - d)None of the mentioned
Correct answer is option 'A'. Can you explain this answer?
A CFG for a program describing strings of letters with the word “main” somewhere in the string:
a)
-> m a i n
-> | epsilon
-> A | B | … | Z | a | b … | z
-> | epsilon
-> A | B | … | Z | a | b … | z
b)
> m a i n
–>
–> A | B | … | Z | a | b … | z
–>
–> A | B | … | Z | a | b … | z
c)
–> m a i n
–> | epsilon
–> A | B | … | Z | a | b … | z
–> | epsilon
–> A | B | … | Z | a | b … | z
d)
None of the mentioned
|
|
Raghav Basu answered |
Explanation:
There are multiple ways to design a CFG for generating strings with the word "main" somewhere in the string. Let's analyze each option and understand why option A is the correct choice.
a) -> m a i n -> | epsilon -> A | B | ... | Z | a | b ... | z
This CFG states that a valid string can start with the letter "m", followed by "a", "i", and "n" in that order. It also allows for the possibility of generating strings without the word "main" by using epsilon, as well as including any other letters from the alphabet.
b) -> m a i n -> -> -> A | B | ... | Z | a | b ... | z
This CFG seems to have a typo in the production rules, as the second arrow "->" is not a valid production rule in CFGs.
c) -> -> m a i n -> | epsilon -> A | B | ... | Z | a | b ... | z
This CFG does not provide a valid path to generate the word "main" in the string, as it only allows for epsilon or individual letters from the alphabet.
d) None of the mentioned
This option is not correct, as option A provides a valid CFG for generating strings with the word "main" somewhere in the string.
Therefore, the correct answer is option A, as it provides a valid CFG that can generate strings containing the word "main" in them.
There are multiple ways to design a CFG for generating strings with the word "main" somewhere in the string. Let's analyze each option and understand why option A is the correct choice.
a) -> m a i n -> | epsilon -> A | B | ... | Z | a | b ... | z
This CFG states that a valid string can start with the letter "m", followed by "a", "i", and "n" in that order. It also allows for the possibility of generating strings without the word "main" by using epsilon, as well as including any other letters from the alphabet.
b) -> m a i n -> -> -> A | B | ... | Z | a | b ... | z
This CFG seems to have a typo in the production rules, as the second arrow "->" is not a valid production rule in CFGs.
c) -> -> m a i n -> | epsilon -> A | B | ... | Z | a | b ... | z
This CFG does not provide a valid path to generate the word "main" in the string, as it only allows for epsilon or individual letters from the alphabet.
d) None of the mentioned
This option is not correct, as option A provides a valid CFG for generating strings with the word "main" somewhere in the string.
Therefore, the correct answer is option A, as it provides a valid CFG that can generate strings containing the word "main" in them.
What is the minimum number of productions present in the below given context free grammar to make it Chomsky Normal Form?
S → XYx
X → xxy
Y → Xz- a)7
- b)8
- c)9
- d)10
Correct answer is option 'B'. Can you explain this answer?
What is the minimum number of productions present in the below given context free grammar to make it Chomsky Normal Form?
S → XYx
X → xxy
Y → Xz
S → XYx
X → xxy
Y → Xz
a)
7
b)
8
c)
9
d)
10
|
|
Crack Gate answered |
Concepts:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal
Calculation:
S → XA
A → YB
B → x
X → BC
C → BD
D → y
Y → XE
E → z
S → XA
A → YB
B → x
X → BC
C → BD
D → y
Y → XE
E → z
The transition a Push down automaton makes is additionally dependent upon the:- a)stack
- b)input tape
- c)terminals
- d)none of the mentioned
Correct answer is option 'A'. Can you explain this answer?
The transition a Push down automaton makes is additionally dependent upon the:
a)
stack
b)
input tape
c)
terminals
d)
none of the mentioned
|
|
Shraddha Iyer answered |
Introduction:
A pushdown automaton (PDA) is a type of automaton that extends the capabilities of a finite automaton by incorporating a stack. It is used to recognize context-free languages and is an important concept in the theory of computation. The transition made by a PDA is not only dependent upon the input tape but also on the stack.
Explanation:
A pushdown automaton consists of the following components:
1. Input Tape: This is where the input string is placed. The PDA reads the input symbols one by one from left to right.
2. Stack: The stack is a data structure that allows operations like push (inserting an element at the top) and pop (removing the topmost element). It is used to store and manipulate information during the computation of the PDA.
3. Finite Control: It is responsible for controlling the overall behavior of the PDA. It determines the transitions to be made based on the current state, input symbol, and the top symbol of the stack.
Transition Function:
The transition function of a PDA determines the next state and the changes to be made in the stack based on the current state, input symbol, and the top symbol of the stack. It is denoted as δ(q, a, X) → (p, Y), where:
- q is the current state
- a is the current input symbol
- X is the top symbol of the stack
- p is the next state
- Y is the string to be pushed onto the stack
Dependency on the Stack:
The transition made by a PDA is additionally dependent upon the stack because the next state and the changes to be made in the stack are determined by the current state, input symbol, and the top symbol of the stack. The PDA can perform different actions based on the contents of the stack.
For example, if the PDA is in state q, the current input symbol is a, and the top symbol of the stack is X, the transition function δ(q, a, X) → (p, Y) can specify the following actions:
- The PDA can move to the next state p and replace X with the string Y on the top of the stack.
- The PDA can move to the next state p without changing the stack (ε indicates an empty string).
The stack allows the PDA to keep track of previously seen symbols and make decisions based on that information. It provides a form of memory that enables the PDA to recognize context-free languages.
Conclusion:
In conclusion, the transition made by a pushdown automaton is additionally dependent upon the stack. The stack plays a crucial role in determining the next state and the changes to be made in the stack during the computation of the PDA. Without considering the stack, the PDA would not have the ability to recognize context-free languages.
A pushdown automaton (PDA) is a type of automaton that extends the capabilities of a finite automaton by incorporating a stack. It is used to recognize context-free languages and is an important concept in the theory of computation. The transition made by a PDA is not only dependent upon the input tape but also on the stack.
Explanation:
A pushdown automaton consists of the following components:
1. Input Tape: This is where the input string is placed. The PDA reads the input symbols one by one from left to right.
2. Stack: The stack is a data structure that allows operations like push (inserting an element at the top) and pop (removing the topmost element). It is used to store and manipulate information during the computation of the PDA.
3. Finite Control: It is responsible for controlling the overall behavior of the PDA. It determines the transitions to be made based on the current state, input symbol, and the top symbol of the stack.
Transition Function:
The transition function of a PDA determines the next state and the changes to be made in the stack based on the current state, input symbol, and the top symbol of the stack. It is denoted as δ(q, a, X) → (p, Y), where:
- q is the current state
- a is the current input symbol
- X is the top symbol of the stack
- p is the next state
- Y is the string to be pushed onto the stack
Dependency on the Stack:
The transition made by a PDA is additionally dependent upon the stack because the next state and the changes to be made in the stack are determined by the current state, input symbol, and the top symbol of the stack. The PDA can perform different actions based on the contents of the stack.
For example, if the PDA is in state q, the current input symbol is a, and the top symbol of the stack is X, the transition function δ(q, a, X) → (p, Y) can specify the following actions:
- The PDA can move to the next state p and replace X with the string Y on the top of the stack.
- The PDA can move to the next state p without changing the stack (ε indicates an empty string).
The stack allows the PDA to keep track of previously seen symbols and make decisions based on that information. It provides a form of memory that enables the PDA to recognize context-free languages.
Conclusion:
In conclusion, the transition made by a pushdown automaton is additionally dependent upon the stack. The stack plays a crucial role in determining the next state and the changes to be made in the stack during the computation of the PDA. Without considering the stack, the PDA would not have the ability to recognize context-free languages.
Which of the following are non essential while simplifying a grammar?- a)Removal of useless symbols
- b)Removal of unit productions
- c)Removal of null production
- d)None of the mentioned
Correct answer is option 'D'. Can you explain this answer?
Which of the following are non essential while simplifying a grammar?
a)
Removal of useless symbols
b)
Removal of unit productions
c)
Removal of null production
d)
None of the mentioned
|
|
Rajesh Malik answered |
Here are some process used to simplify a CFG but to produce an equivalent grammar:
a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.
a) Removal of useless symbols(non terminal) b) Removal of Unit productions and c) Removal of Null productions.
From the definition of context free grammars,
G=(V, T, P, S)
What is the solution of VÇT?- a)Null
- b)Not Null
- c)Cannot be determined, depends on the language
- d)None of the mentioned
Correct answer is option 'A'. Can you explain this answer?
From the definition of context free grammars,
G=(V, T, P, S)
What is the solution of VÇT?
G=(V, T, P, S)
What is the solution of VÇT?
a)
Null
b)
Not Null
c)
Cannot be determined, depends on the language
d)
None of the mentioned
|
|
Prasad Unni answered |
V is the set of non terminal symbols while T is the st of terminal symbols, their intersection would always be null.
If P is the production, for the given statement, state true or false.P: V->(V∑T)* represents that the left hand side production rule has no right or left context.- a)true
- b)false
Correct answer is option 'A'. Can you explain this answer?
If P is the production, for the given statement, state true or false.P: V->(V∑T)* represents that the left hand side production rule has no right or left context.
a)
true
b)
false
|
|
Maulik Pillai answered |
Here the production P is from the definition of Context free grammar and thus, has no right or left context.
Context free grammar is called Type 2 grammar because of ______________ hierarchy.- a)Greibach
- b)Backus
- c)Chomsky
- d)None of the mentioned
Correct answer is option 'C'. Can you explain this answer?
Context free grammar is called Type 2 grammar because of ______________ hierarchy.
a)
Greibach
b)
Backus
c)
Chomsky
d)
None of the mentioned
|
|
Raghav Basu answered |
Chomsky Hierarchy and Type 2 Grammar
Chomsky hierarchy is a classification of formal grammars based on their generative power. It is named after Noam Chomsky, who introduced the concept in the 1950s. Chomsky hierarchy consists of four types of grammars, with Type 2 grammar being context-free grammar.
Type 2 Grammar
Context-free grammar is classified as Type 2 grammar in the Chomsky hierarchy. Type 2 grammars are characterized by rules that have a single non-terminal on the left-hand side and a sequence of terminals and non-terminals on the right-hand side. These grammars are used to generate context-free languages, which are languages that can be described by a context-free grammar.
Relation to Chomsky
Chomsky hierarchy is named after Noam Chomsky because he was instrumental in developing the theory of formal languages and grammars. He introduced the concept of context-free grammars as part of this theory, leading to the classification of grammars into four types based on their generative power.
Classification
Type 2 grammar, or context-free grammar, is called Type 2 because it falls in the second level of the Chomsky hierarchy. This hierarchy categorizes grammars based on their expressive power, with Type 2 being more powerful than Type 3 (regular grammar) but less powerful than Type 1 (context-sensitive grammar) and Type 0 (unrestricted grammar).
In conclusion, context-free grammar is named Type 2 grammar in the Chomsky hierarchy due to its position in the classification of formal grammars based on their generative power.
Chomsky hierarchy is a classification of formal grammars based on their generative power. It is named after Noam Chomsky, who introduced the concept in the 1950s. Chomsky hierarchy consists of four types of grammars, with Type 2 grammar being context-free grammar.
Type 2 Grammar
Context-free grammar is classified as Type 2 grammar in the Chomsky hierarchy. Type 2 grammars are characterized by rules that have a single non-terminal on the left-hand side and a sequence of terminals and non-terminals on the right-hand side. These grammars are used to generate context-free languages, which are languages that can be described by a context-free grammar.
Relation to Chomsky
Chomsky hierarchy is named after Noam Chomsky because he was instrumental in developing the theory of formal languages and grammars. He introduced the concept of context-free grammars as part of this theory, leading to the classification of grammars into four types based on their generative power.
Classification
Type 2 grammar, or context-free grammar, is called Type 2 because it falls in the second level of the Chomsky hierarchy. This hierarchy categorizes grammars based on their expressive power, with Type 2 being more powerful than Type 3 (regular grammar) but less powerful than Type 1 (context-sensitive grammar) and Type 0 (unrestricted grammar).
In conclusion, context-free grammar is named Type 2 grammar in the Chomsky hierarchy due to its position in the classification of formal grammars based on their generative power.
The production of the form A->B , where A and B are non terminals is called- a)Null production
- b)Unit production
- c)Greibach Normal Form
- d)Chomsky Normal Form
Correct answer is option 'B'. Can you explain this answer?
The production of the form A->B , where A and B are non terminals is called
a)
Null production
b)
Unit production
c)
Greibach Normal Form
d)
Chomsky Normal Form
|
|
Ameya Goyal answered |
A->ε is termed as Null production while A->B is termed as Unit production.
Let G be a Context Free Grammar in Chomsky Normal Form. To derive a string (aaaaaa)n where a is terminal variable and n is 5, the number of products to be used is _____.
Correct answer is '59'. Can you explain this answer?
Let G be a Context Free Grammar in Chomsky Normal Form. To derive a string (aaaaaa)n where a is terminal variable and n is 5, the number of products to be used is _____.
|
|
Pankaj Patel answered |
Solution:
Chomsky Normal Form of a Context Free Grammar allows only two types of productions:
1. A → BC
2. A → a
where A, B, and C are non-terminal variables and a is a terminal variable.
To derive a string (aaaaaa)n where a is terminal variable and n is 5, we can follow the following steps:
Step 1: Start with the start variable S and apply the production S → AB where A and B are two new variables.
Step 2: Apply the production A → a and B → CD where C and D are two new variables.
Step 3: Apply the production C → a and D → EF where E and F are two new variables.
Step 4: Apply the production E → a and F → GH where G and H are two new variables.
Step 5: Apply the production G → a and H → IJ where I and J are two new variables.
Step 6: Apply the production I → a and J → a.
Step 7: Repeat steps 5 and 6 n-1 times to get the string (aaaaaa)n.
So, to derive the string (aaaaaa)5, we need to use a total of 59 productions.
Therefore, the correct answer is '59'.
Chomsky Normal Form of a Context Free Grammar allows only two types of productions:
1. A → BC
2. A → a
where A, B, and C are non-terminal variables and a is a terminal variable.
To derive a string (aaaaaa)n where a is terminal variable and n is 5, we can follow the following steps:
Step 1: Start with the start variable S and apply the production S → AB where A and B are two new variables.
Step 2: Apply the production A → a and B → CD where C and D are two new variables.
Step 3: Apply the production C → a and D → EF where E and F are two new variables.
Step 4: Apply the production E → a and F → GH where G and H are two new variables.
Step 5: Apply the production G → a and H → IJ where I and J are two new variables.
Step 6: Apply the production I → a and J → a.
Step 7: Repeat steps 5 and 6 n-1 times to get the string (aaaaaa)n.
So, to derive the string (aaaaaa)5, we need to use a total of 59 productions.
Therefore, the correct answer is '59'.
A push down automaton with only symbol allowed on the stack along with fixed symbol.- a)Embedded PDA
- b)Nested Stack automata
- c)DPDA
- d)Counter Automaton
Correct answer is option 'D'. Can you explain this answer?
A push down automaton with only symbol allowed on the stack along with fixed symbol.
a)
Embedded PDA
b)
Nested Stack automata
c)
DPDA
d)
Counter Automaton
|
|
Amrutha Singh answered |
This class of automata can recognize a set of context free languages like {anbn|n belongs to N}
Which of the following automata takes stack as auxiliary storage?- a)Finite automata
- b)Push down automata
- c)Turing machine
- d)All of the mentioned
Correct answer is option 'B'. Can you explain this answer?
Which of the following automata takes stack as auxiliary storage?
a)
Finite automata
b)
Push down automata
c)
Turing machine
d)
All of the mentioned
|
|
Tarun Saini answered |
Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing machines use Queue for the same.
tate true or false:Statement: Every context free grammar can be transformed into an equvalent non deterministic push down automata.- a)true
- b)false
Correct answer is option 'A'. Can you explain this answer?
tate true or false:Statement: Every context free grammar can be transformed into an equvalent non deterministic push down automata.
a)
true
b)
false
|
|
Aman Menon answered |
Push down automata is the automaton machine for all the context free grammar or Type 2 languages.
State true or false:Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.- a)true
- b)false
Correct answer is option 'A'. Can you explain this answer?
State true or false:Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.
a)
true
b)
false
|
|
Ayush Basu answered |
We apply the productions of CFG to infer that certain strings are in the language of a certain variable.
Which of the expression is appropriate?For production p: a->b where a∈V and b∈_______- a)V
- b)S
- c)(V+∑)*
- d)V+ ∑
Correct answer is option 'C'. Can you explain this answer?
Which of the expression is appropriate?For production p: a->b where a∈V and b∈_______
a)
V
b)
S
c)
(V+∑)*
d)
V+ ∑
|
|
Amrutha Sharma answered |
According to the definition, the starting variable can produce another variable or any terminal or a variable which leads to terminal.
The pumping lemma is often used to prove that a language is:- a)Context free
- b)Not context free
- c)Regular
- d)None of the mentioned
Correct answer is option 'B'. Can you explain this answer?
The pumping lemma is often used to prove that a language is:
a)
Context free
b)
Not context free
c)
Regular
d)
None of the mentioned
|
Aryan Saha answered |
Introduction:
The pumping lemma is a powerful tool used in formal language theory to prove that a given language is not context-free. It is a necessary but not sufficient condition for a language to be context-free. The pumping lemma helps in identifying certain patterns in the strings of a language that cannot be generated by a context-free grammar.
Explanation:
The pumping lemma states that for any context-free language L, there exists a constant n (the pumping length) such that any string s in L of length greater than or equal to n can be divided into five parts: s = uvwxy, where:
1. |vwx| ≤ n,
2. |vx| ≥ 1, and
3. for all i ≥ 0, uv^iwx^iy ∈ L.
Proof by contradiction:
To prove that a language L is not context-free using the pumping lemma, we assume that L is context-free and then show that it leads to a contradiction.
1. Assume L is context-free.
2. Let n be the pumping length for L.
3. Choose a string s in L such that |s| ≥ n.
4. Divide s into five parts: s = uvwxy, satisfying the conditions of the pumping lemma.
5. Consider the string s' = uv^0wx^0y = uwxy.
6. Since |vx| ≥ 1, pumping down i.e., setting i = 0, will result in a string s' that is no longer in L.
7. This contradicts the assumption that L is context-free.
8. Therefore, the initial assumption that L is context-free must be false.
Conclusion:
If we can find a single string s in a language L that cannot be pumped or satisfies the pumping lemma, then we can conclude that L is not context-free. Hence, option 'B' is the correct answer. The pumping lemma is a valuable tool for proving that certain languages are not context-free and helps in understanding the limitations of context-free grammars in language generation.
The pumping lemma is a powerful tool used in formal language theory to prove that a given language is not context-free. It is a necessary but not sufficient condition for a language to be context-free. The pumping lemma helps in identifying certain patterns in the strings of a language that cannot be generated by a context-free grammar.
Explanation:
The pumping lemma states that for any context-free language L, there exists a constant n (the pumping length) such that any string s in L of length greater than or equal to n can be divided into five parts: s = uvwxy, where:
1. |vwx| ≤ n,
2. |vx| ≥ 1, and
3. for all i ≥ 0, uv^iwx^iy ∈ L.
Proof by contradiction:
To prove that a language L is not context-free using the pumping lemma, we assume that L is context-free and then show that it leads to a contradiction.
1. Assume L is context-free.
2. Let n be the pumping length for L.
3. Choose a string s in L such that |s| ≥ n.
4. Divide s into five parts: s = uvwxy, satisfying the conditions of the pumping lemma.
5. Consider the string s' = uv^0wx^0y = uwxy.
6. Since |vx| ≥ 1, pumping down i.e., setting i = 0, will result in a string s' that is no longer in L.
7. This contradicts the assumption that L is context-free.
8. Therefore, the initial assumption that L is context-free must be false.
Conclusion:
If we can find a single string s in a language L that cannot be pumped or satisfies the pumping lemma, then we can conclude that L is not context-free. Hence, option 'B' is the correct answer. The pumping lemma is a valuable tool for proving that certain languages are not context-free and helps in understanding the limitations of context-free grammars in language generation.
State true or false:S-> 0S1|01Statement: No regular expression exists for the given grammar.- a)true
- b)false
Correct answer is option 'A'. Can you explain this answer?
State true or false:S-> 0S1|01Statement: No regular expression exists for the given grammar.
a)
true
b)
false
|
|
Bibek Chakraborty answered |
The statement is incomplete. Please provide the complete statement.
Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.- a)(a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
- b)(bbbb+aaaa)*
- c)((a+b)(a+b)(a+b)(a+b))*
- d)None of the mentioned
Correct answer is option 'C'. Can you explain this answer?
Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.
a)
(a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b)
(bbbb+aaaa)*
c)
((a+b)(a+b)(a+b)(a+b))*
d)
None of the mentioned
|
|
Krithika Gupta answered |
Explanation:
Regular Expression Explanation:
- The regular expression ((a+b)(a+b)(a+b)(a+b))* matches strings of length n where n is a multiple of 4.
- Each (a+b) in the regular expression represents a single character from the set {a, b}.
- Since there are four (a+b) groups in the regular expression, it ensures that the string length is a multiple of 4.
Option Analysis:
- Option (a) includes multiple combinations of a and b but does not specifically require the length to be a multiple of 4.
- Option (b) only allows strings consisting of only 'a's or 'b's, which does not cover all possible strings with length n being a multiple of 4.
- Option (c) is the correct choice as it enforces the condition of having the string length as a multiple of 4 by repeating the (a+b) group four times.
Therefore, the correct regular expression that allows strings on {a,b}* with length n where n is a multiple of 4 is option (c) ((a+b)(a+b)(a+b)(a+b))*.
Which of the following statement is false?- a)Context free language is the subset of context sensitive language
- b)Regular language is the subset of context sensitive language
- c)Recursively ennumerable language is the super set of regular language
- d)Context sensitive language is a subset of context free language
Correct answer is option 'D'. Can you explain this answer?
Which of the following statement is false?
a)
Context free language is the subset of context sensitive language
b)
Regular language is the subset of context sensitive language
c)
Recursively ennumerable language is the super set of regular language
d)
Context sensitive language is a subset of context free language
|
|
Ankit Mehta answered |
Explanation: Every regular language can be produced by context free grammar and context free language can be produced by context sensitive grammar and so on.
Chapter doubts & questions for Context Free Grammar, Languages and Pushdown Automata - 6 Months Preparation for GATE CSE 2025 is part of Computer Science Engineering (CSE) exam preparation. The chapters have been prepared according to the Computer Science Engineering (CSE) exam syllabus. The Chapter doubts & questions, notes, tests & MCQs are made for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests here.
Chapter doubts & questions of Context Free Grammar, Languages and Pushdown Automata - 6 Months Preparation for GATE CSE in English & Hindi are available as part of Computer Science Engineering (CSE) exam.
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
6 Months Preparation for GATE CSE
453 videos|1305 docs|700 tests
|
|
© EduRev
|
Education Revolution
|
|
Signup on EduRev and stay on top of your study goals
10M+ students crushing their study goals daily