Register

NIELIT 2017 DEC Scientific Assistant A - Section B: 19

• recategorized by
1,242 views
1 votes
1 votes

Let $P, Q, R$ be a regular expression over $\Sigma$. If $P$ does not contain null string, then $R=Q+RP$ has a unique solution ___________ .

  1. $Q^{*}P$
  2. $QP^{*}$
  3. $Q^{*}P^{*}$
  4. $\left ( P^{*}O^{*} \right)^{*}$
• recategorized by
User Avatar

1 Answer

3 votes
3 votes

According to arden's theorem, we can directly find the answer is QP*
Arden's Theorem
Statement:
Let $P$ and $Q$ be two regular expressions.
If $P$ does not contain null string, then $R = Q + RP$ has a unique solution that is $R = Qp*$
Proof:
$R=Q+(Q+RP)P$ [After putting the value $R=Q+RP$]
$=Q+QP+RP^{2}$
When we put the value of $R$ recursively again and again, we get the following equation:
$R=Q+QP+QP^{2}+QP^{3}....$
$R=Q(\epsilon +P+P^{2}+P^{3}+....)$
$ R=QP^{*}   [ P^{*}  =  (\epsilon +P+P^{2}+P^{3}+....)] $

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
2 answers
1
admin asked Mar 31, 2020
975 views
NIELIT 2017 DEC Scientific Assistant A - Section B: 35
$\left (0+ \varepsilon \right) \left (1+ \varepsilon \right)$ represents : $\left \{0,1,01,\varepsilon \right \}$ $\left \{0,1,\varepsilon \right \}$ $\left \{0,1,01, 11, 00 ,10,\varepsilon \right \}$ $\left \{0,1, \right \}$
$\left (0+ \varepsilon \right) \left (1+ \varepsilon \right)$ represents :$\left \{0,1,01,\varepsilon \right \}$$\left \{0,1,\varepsilon \right \}$$\left \{0,1,01, 11, ...
User Avatar
2 votes
2 votes
1 answer
2
admin asked Mar 31, 2020
841 views
NIELIT 2017 DEC Scientific Assistant A - Section B: 54
Complement of $\left (a+b \right)^{*}$ will be : $Phi\left ( \Phi \right )$ Null $a$ $b$
Complement of $\left (a+b \right)^{*}$ will be : $Phi\left ( \Phi \right )$Null$a$$b$
User Avatar
2 votes
2 votes
4 answers
3
admin asked Mar 31, 2020
1,665 views
NIELIT 2017 DEC Scientific Assistant A - Section B: 3
The automaton which allows transformation to a new state without consuming any input symbols : $NFA$ $DFA$ $NFA - 1$ All of the options
The automaton which allows transformation to a new state without consuming any input symbols : $NFA$$DFA$$NFA - 1$All of the options
User Avatar
2 votes
2 votes
3 answers
4
admin asked Mar 31, 2020
1,599 views
NIELIT 2017 DEC Scientific Assistant A - Section B: 4
Complement of a $DFA$ can be obtained by : making starting state as final state. make final as a starting state. making final states non-final and non-final as final. None of the options
Complement of a $DFA$ can be obtained by :making starting state as final state.make final as a starting state.making final states non-final and non-final as final.None of...
User Avatar
Link Copied!