edited by
9,294 views
31 votes
31 votes

Let $L$ be a regular language. Consider the constructions on $L$ below:

  1. repeat $(L) = \{ww \mid  w \in  L\}$
  2. prefix $(L) = \{u \mid ∃v : uv \in L\}$
  3. suffix $(L) = \{v \mid  ∃u : uv \in L\}$
  4. half $(L) = \{u \mid ∃v : | v | = | u | \text{ and } uv \in L\}$

Which of the constructions could lead to a non-regular language?

  1. Both I and IV
  2. Only I
  3. Only IV
  4. Both II and III
edited by

2 Answers

Best answer
22 votes
22 votes

Correct answer is B. Only $I$.

Repeat $(L) = \{ww \mid w \in L\}$ is non regular language

Half$(L)$, suffix$(L)$, and prefix$(L)$ are regular languages

Reference:

https://gateoverflow.in/3637/gate2006-it_81

edited by
22 votes
22 votes
  • repeat(L) should not be confused with concatenation as there is a specific order to it. Only same strings are concatenated with each other and not all. Moreover, double word language is not even a CFG [non-regular].
  • prefix(L) is a regular language – all the states in L’s DFA could be made final, giving result to a DFA which would accept prefix(L) [regular]
  • suffix(L) is a regular language as a NFA could be constructed which would accept suffix(L). Every state in L’s DFA can get an incident # – edge from start state – this NFA would accept suffix(L) [regular].
  • half(L) is a regular language. It is just a language containing even length strings
  • so answer is B
Answer:

Related questions

29 votes
29 votes
1 answer
2
Ishrat Jahan asked Oct 31, 2014
7,900 views
Which of the following statements about regular languages is NOT true ?Every language has a regular supersetEvery language has a regular subsetEvery subset of a regular l...
45 votes
45 votes
4 answers
3