Data-Link-Layer
January 16, 2024DSSSB TGT 2021
January 16, 2024UGC NET CS 2005 june-paper-2
|
Question 2
|
Identify the language which is not context-free.
|
L = { wwR ǀ wε{0,1}* }
|
|
|
L = { a n b n ǀ n≥0 }
|
|
|
L = { ww ǀ wε{0,1}* }
|
|
|
L = { a n b m c m d n ǀ n,m ≥0 }
|
Question 2 Explanation:
Option-A is a CFL because for this we can have a non deterministic pushdown automata which will accept the string by exploring all the possibilities on each input character.
Option-B is correct because we can have a deterministic pushdown automata which will push all the “a” as they come as input and when “b” comes as input for every “b” one “a” will be popped. So in this way we can design a pushdown automata which will accept a n b n . Hence a n b n is a CFL.
Option-C is not a CFL because we can’t design a pushdown which can accept CFL. Suppose a string “abcabc”. Now let’s say pushdown automata recognize w=abc after symbol “c” now when
“a” come as input after “c” the pushdown automata have to pop “a” i.e. initial input symbol “a” but top of the stack contains “c” as top element. So in this way we can’t have any pushdown automata which can accept “ww” language. So it is not a CFL.
Option-D is a CFL because we can design a pushdown automata for a n b m c m d n . The push down automata will push “a” and “b” as the come as input symbol. When “c” came as input then for each “c” one “b” is popped from top of the stack. And when “d” will come as input symbol the top of stack will contain only a’s so for every “d” one “a” is popped . In this way we can design a pushdown automata for a n b m c m d n .
So, option-C is correct answer.
Option-B is correct because we can have a deterministic pushdown automata which will push all the “a” as they come as input and when “b” comes as input for every “b” one “a” will be popped. So in this way we can design a pushdown automata which will accept a n b n . Hence a n b n is a CFL.
Option-C is not a CFL because we can’t design a pushdown which can accept CFL. Suppose a string “abcabc”. Now let’s say pushdown automata recognize w=abc after symbol “c” now when
“a” come as input after “c” the pushdown automata have to pop “a” i.e. initial input symbol “a” but top of the stack contains “c” as top element. So in this way we can’t have any pushdown automata which can accept “ww” language. So it is not a CFL.
Option-D is a CFL because we can design a pushdown automata for a n b m c m d n . The push down automata will push “a” and “b” as the come as input symbol. When “c” came as input then for each “c” one “b” is popped from top of the stack. And when “d” will come as input symbol the top of stack will contain only a’s so for every “d” one “a” is popped . In this way we can design a pushdown automata for a n b m c m d n .
So, option-C is correct answer.
Correct Answer: C
Question 2 Explanation:
Option-A is a CFL because for this we can have a non deterministic pushdown automata which will accept the string by exploring all the possibilities on each input character.
Option-B is correct because we can have a deterministic pushdown automata which will push all the “a” as they come as input and when “b” comes as input for every “b” one “a” will be popped. So in this way we can design a pushdown automata which will accept a n b n . Hence a n b n is a CFL.
Option-C is not a CFL because we can’t design a pushdown which can accept CFL. Suppose a string “abcabc”. Now let’s say pushdown automata recognize w=abc after symbol “c” now when
“a” come as input after “c” the pushdown automata have to pop “a” i.e. initial input symbol “a” but top of the stack contains “c” as top element. So in this way we can’t have any pushdown automata which can accept “ww” language. So it is not a CFL.
Option-D is a CFL because we can design a pushdown automata for a n b m c m d n . The push down automata will push “a” and “b” as the come as input symbol. When “c” came as input then for each “c” one “b” is popped from top of the stack. And when “d” will come as input symbol the top of stack will contain only a’s so for every “d” one “a” is popped . In this way we can design a pushdown automata for a n b m c m d n .
So, option-C is correct answer.
Option-B is correct because we can have a deterministic pushdown automata which will push all the “a” as they come as input and when “b” comes as input for every “b” one “a” will be popped. So in this way we can design a pushdown automata which will accept a n b n . Hence a n b n is a CFL.
Option-C is not a CFL because we can’t design a pushdown which can accept CFL. Suppose a string “abcabc”. Now let’s say pushdown automata recognize w=abc after symbol “c” now when
“a” come as input after “c” the pushdown automata have to pop “a” i.e. initial input symbol “a” but top of the stack contains “c” as top element. So in this way we can’t have any pushdown automata which can accept “ww” language. So it is not a CFL.
Option-D is a CFL because we can design a pushdown automata for a n b m c m d n . The push down automata will push “a” and “b” as the come as input symbol. When “c” came as input then for each “c” one “b” is popped from top of the stack. And when “d” will come as input symbol the top of stack will contain only a’s so for every “d” one “a” is popped . In this way we can design a pushdown automata for a n b m c m d n .
So, option-C is correct answer.
Subscribe
Login
0 Comments