...
Question 4848 – UGC NET CS 2018-DEC Paper-2
November 30, 2023
Software-Engineering
November 30, 2023
Question 4848 – UGC NET CS 2018-DEC Paper-2
November 30, 2023
Software-Engineering
November 30, 2023

UGC NET CS 2018-DEC Paper-2

Question 7
Consider the following two languages:
L​ 1​ = {x | for some y with | y| = 2 |x| ,xy∈ L and L is regular language}
L​ 2​ = { x | for some y such that |x| = |y|, xy∈ L and L is regular language}
Which one of the following is correct?
A
Both L​ 1​ and L​ 2​ are regular languages
B
Both L​ 1​ and L​ 2​ are not regular languages
C
Only L​ 1​ is regular language
D
Only L​ 2​ is regular language
Question 7 Explanation: 
if L is a regular language then we always have a string “w” which can be broken into “xy” such that |y|=2|x|
Consider a language L= {a​ 3n​ | n ≥ 0} , the strings in L are {ε, aaa, aaaaaa, …….}
then L​ 1​ = {a​ n​ | n ≥ 0} as every string in L can be broken into three equal parts .
DFA for L

DFA for L​ 1

By same logic L​ 2​ is also regular, here we have to break each string of L into two equal parts and also every even length string from L will belongs to L​ 1​ , since we can break only even length string into two equal parts such that |x| = |y| if “xy ε L”
Correct Answer: A
Question 7 Explanation: 
if L is a regular language then we always have a string “w” which can be broken into “xy” such that |y|=2|x|
Consider a language L= {a​ 3n​ | n ≥ 0} , the strings in L are {ε, aaa, aaaaaa, …….}
then L​ 1​ = {a​ n​ | n ≥ 0} as every string in L can be broken into three equal parts .
DFA for L

DFA for L​ 1

By same logic L​ 2​ is also regular, here we have to break each string of L into two equal parts and also every even length string from L will belongs to L​ 1​ , since we can break only even length string into two equal parts such that |x| = |y| if “xy ε L”

Leave a Reply

Your email address will not be published. Required fields are marked *