Register

CMI 2024-PART B-02.

71 views
0 votes
0 votes
Let M1 = (Q1, {q1}, ∆1, F1), where ∆1 ⊆ Q1 × (Σ ∪ {ϵ}) × Q1, be a non-deterministic finite automaton (NFA) accepting a language L1 ⊆ {0, 1} ∗ . Let ϵ denote the null string. We construct a new NFA M2 = (Q2, {q2}, ∆2, F2), where ∆2 ⊆ Q2 × (Σ ∪ {ϵ}) × Q2, as follows.

• Q2 = Q1.

 • q2 = q1.

 • F2 = F1 ∪ {q1}.

• (p, a, p′ ) ∈ ∆2 iff either (p, a, p′ ) ∈ ∆1 or (p ∈ F1 and a = ϵ and p ′ = q1) Prove or disprove: The language L2 accepted by M2 is L*
User Avatar

Please log in or register to answer this question.

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

Related questions

63
views
0 answers
0 votes
Hemant2407 asked May 27
63 views
CMI2024-B-02
Let M1 = (Q1, {q1}, ∆1, F1), where ∆1 ⊆ Q1 (Σ ∪ {ϵ}) Q1, be a non-deterministic finite automaton (NFA) accepting a language L1 ⊆ {0, 1} ∗ . Let ϵ denote ... = ϵ and p ′ = q1) Prove or disprove: The language L2 accepted by M2 is L ∗ 1 .
User Avatar
433
views
1 answers
0 votes
Hritik1204 asked Jan 5
433 views
Find the number of final states in DFA that recognizes L, where L= {w1a w2:|w1|≥3,|w2|≤5}, ∑={a, b} and w1, w2 ∈ ∑ * ______
User Avatar
842
views
1 answers
0 votes
M_Umair_Khan42900 asked Dec 29, 2022
842 views
Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b]. s(a) p(pp)*( A + p)q + q and p*q (b) A +0(0+1)* + (0+1)* 00(0+1)* and ((1*0)*01*)* (c) (s*ttt)*s* and s*(ttts*)*
Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b].s(a) p(pp)*( A + p)q + q and p*q(b) A +0(0+1)* + (0+1)* 00(0+1)* and ((1*0)*01*)*(c) (s*ttt)*s* and s*(ttts*)*
User Avatar
254
views
0 answers
0 votes
M_Umair_Khan42900 asked Dec 29, 2022
254 views
For each of the following language, if the language is regular, write down the corresponding regular expression. Else, prove that the language is not regular. a) (0²ⁿ | n ≥ 1) Answer: b) String over the decimal alphabets (0,1,2....9) with characters in sorted orders. c) The set of all even binary numbers
For each of the following language, if the language is regular, write down the corresponding regular expression. Else, prove that the language is not regular.a) ( ... 9) with characters in sorted orders.c) The set of all even binary numbers
User Avatar
Link Copied!