recategorized by
3,339 views
2 votes
2 votes

Given the following statements:

$S_1$: If $L$ is a regular language then the language $\{uv \mid u \in L, v \in L^R\}$ is also regular.

$S_2$: $L=\{ww^R\}$ is regular language.

Which of the following is true?

  1. $S_1$ is not correct and $S_2$ is not correct
  2. $S_1$ is not correct and $S_2$ is correct
  3. $S_1$ is correct and $S_2$ is not correct
  4. $S_1$ is correct and $S_2$ is correct
recategorized by

1 Answer

Best answer
7 votes
7 votes

Answer C: S1 is correct and S2 is not correct

  • If L is regular then reversal of L is also regular. hence u and v are regular
  • Concatenation of regular languages are regular.
  • Hence uv is regular

S1 is correct

  • To find wwR we need to remember what is w.
  • Regular grammar is checked by finite automata, which has no memory (stack)
  • To find wwR we need at least NPDA

S2 is incorrect

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
2
go_editor asked Jul 26, 2016
2,871 views
Linux operating system usesAffinity schedulingFair Preemptive SchedulingHand ShakingHighest Penalty Ratio Next