Register

GATE CSE 2019 | Question: 7

• edited by
14,907 views
34 votes
34 votes

If $L$ is a regular language over $\Sigma = \{a,b\} $, which one of the following languages is NOT regular?

  1. $L.L^R = \{xy \mid x \in L , y^R \in L\}$
  2. $\{ww^R \mid w \in L \}$
  3. $\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^* $such that$ \ xy \in L\}$
  4. $\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^* $such that$ \ xy \in L\}$
• edited by
User Avatar

5 Answers

1 votes
1 votes
ww^R cannot be recognized without using stack, so it cannot be regular.
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

50 votes
50 votes
6 answers
1
Arjun asked Feb 7, 2019
34,292 views
GATE CSE 2019 | Question: 15
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ? $3$ $5$ $9$ $24$
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping...
User Avatar
21 votes
21 votes
7 answers
2
Arjun asked Feb 7, 2019
9,168 views
GATE CSE 2019 | Question: GA-1
The expenditure on the project _____ as follows: equipment Rs.$20$ lakhs, salaries Rs.$12$ lakhs, and contingency Rs.$3$ lakhs. break down break breaks down breaks
The expenditure on the project _____ as follows: equipment Rs.$20$ lakhs, salaries Rs.$12$ lakhs, and contingency Rs.$3$ lakhs.break downbreakbreaks downbreaks
User Avatar
11 votes
11 votes
6 answers
3
Arjun asked Feb 7, 2019
5,778 views
GATE CSE 2019 | Question: GA-2
The search engine’s business model ____ around the fulcrum of trust. revolves plays sinks bursts
The search engine’s business model ____ around the fulcrum of trust.revolvesplayssinksbursts
User Avatar
8 votes
8 votes
4 answers
4
Arjun asked Feb 7, 2019
7,321 views
GATE CSE 2019 | Question: GA-3
Two cars at the same time from the same location and go in the same direction. The speed of the first car is $50$ km/h and the speed of the second car is $60$ km/h. The number of hours it takes for the distance between the two cars to be $20$ km is _____. $1$ $2$ $3$ $6$
Two cars at the same time from the same location and go in the same direction. The speed of the first car is $50$ km/h and the speed of the second car is $60$ km/h. The n...
User Avatar
Link Copied!