GATE CSE 2017 Set 2 | Question: 39

Question

GATE CSE 2017 Set 2 | Question: 39

Arjun asked Feb 14, 2017 • edited Apr 14, 2019 by Pooja Khatri

28,286 views

Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below:
$$\begin{array}{|c|c|c|c|}\hline \delta & \text{$\epsilon$} & \text{$a$} & \text{$b$} \\\hline \llap{\rightarrow }\;{ q_0} & \text{$\{q_2\}$} & \text{$\{q_1\}$} & \text{$\{q_0\}$} \\\hline \text{$q_1$} & \text{$\{q_2\}$} & \text{$\{q_2\}$} & \text{$\{q_3\}$} \\\hline \text{$q_2$} & \text{$\{q_0\}$} & \text{$\emptyset$} & \text{$\emptyset$} \\\hline \quad\text{$q_3$}\quad & \text{$\emptyset$} & \text{$\emptyset$} & \text{$\{q_2\}$} \\\hline \end{array}$$
Then $\widehat{\delta}(q_2, aba)$ is

$\emptyset$
$\{q_0, q_1, q_3\}$
$\{q_0, q_1, q_2\}$
$\{q_0, q_2, q_3 \}$

Arjun asked Feb 14, 2017 • edited Apr 14, 2019 by Pooja Khatri

Arjun

28.3k views

See all

12 Answers

Best answer

Starting state $: q_2$ and input string is "$aba$"

$\text{Step 1: }$ Find Epsilon closure of $q_2 = \{q_2,q_0\}$
$\text{Step 2: }$ Find transitions on $a:$
- $q_0\to q_1$
- $q_2 \to \emptyset$
$\text{Step 3: }$ Find epsilon closure of $q_1= \{q_1,q_2,q_0\}$
$\text{Step 4: }$ Find transitions on $b:$
- $q_1\to q_3$
- $q_0\to q_0$
- $q_2\to \emptyset$
$\text{Step 5:}$ Find epsilon closure of $q_0=\{q_0,q_2\}$ UNION epsilon closure of $q_3=\{q_3\}, = \{q_0,q_2,q_3\}$
$\text{Step 6:}$ Find transitions on $a:$
- $q_0 \to q_1$
- $q_2 \to \emptyset$
- $q_3 \to \emptyset$
$\text{Step 7:}$ Find epsilon closure of $q_1: \{q_1,q_0,q_2\}$

Therefore answer is C.

kapilthukral94 answered Feb 15, 2017 • edited Apr 21, 2019 by Arjun

kapilthukral94

See all

Show 6 previous comments

See all

Page:

1
2
3
next »

Related questions

16.5k

views

9 answers

47 votes

Madhav asked Feb 14, 2017

16,517 views

GATE CSE 2017 Set 2 | Question: 25

The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \righ...

Madhav

16.5k views

Madhav asked Feb 14, 2017

8.9k

views

4 answers

36 votes

Madhav asked Feb 14, 2017

8,890 views

GATE CSE 2017 Set 2 | Question: 40

Consider the following languages.$L_1 = \{a^p \mid p \text{ is a prime number} \}$$L_2 = \{ a^nb^mc^{2m} \mid n \geq 0, m \geq 0 \}$$L_3 = \{a^n b^n c^{2n} \mid n \geq 0 ...

Madhav

8.9k views

Madhav asked Feb 14, 2017

8.6k

views

3 answers

33 votes

Madhav asked Feb 14, 2017

8,556 views

GATE CSE 2017 Set 2 | Question: 41

Let $L(R)$ be the language represented by regular expression $R$. Let $L(G)$ be the language generated by a context free grammar $G$. Let $L(M)$ be the language accepted ...

Madhav

8.6k views

Madhav asked Feb 14, 2017

18.4k

views

11 answers

33 votes

khushtak asked Feb 14, 2017

18,383 views

GATE CSE 2017 Set 2 | Question: 16

Identify the language generated by the following grammar, where $S$ is the start variable.$ S \rightarrow XY$$ X \rightarrow aX \mid a$$ Y \rightarrow aYb \mid \epsilon$$...

khushtak

18.4k views

khushtak asked Feb 14, 2017

This is better explained by $\epsilon$-closure in Compiler Design by Ullman — vaibhav101, Feb 3, 2018
First Make The Epsilon NFA then try to solve this question by taking $E-Clousure$ — Ray Tomlinson, Jan 30
So ,sir we have to consider only those states which are used as epsilon move with string aba?

@Arjun — SushB, Dec 26, 2020
extended transition function gives the state the Automaton reaches after processing a string like aba. — kiioo, Jan 22, 2021
The epsilon closure of any state must contain that state so after reading the $a$ and $b$, the epsilon closure of $q_3$ must by $\{q_3\}$ — shadymademe, Aug 6, 2023
@2018 @Prashant what will be the final states in this epsilon NFA?

Can we say q0 and q2 b/c directly on seeing epsilon we are reaching them? — iarnav, Aug 24, 2017
see here no need of the final state since it is asking reachable states but not acceptable. But in question q2 is given as final. — Prashant., Aug 25, 2017
Hi sir @Prashant @Bikram I made a transition diagram same as yours but i am not able to trace out the transition δˆ(q2,aba) .Can you please help me out in this. — Sahil1994, Sep 5, 2017
@Prashant Sir,

EDIT needed: 1 } In question Why q2 is in set notation form in left column , is state q2 and {q2} are same ??

Is this approach correct ?

Better alternative appraoch plz reply

PETER LINZ

For an nfa, the extended transition function is defined so that ∂*(qi,w) contains qj if and only if there is a walk in the transition graph from qi to qj labeled w. This holds for all qi, qj ∈ Q and w∈S

q2 to q2 labeled walk => ∈a∈∈ba∈

q2 to q1 labeled walk => ∈a∈∈ba

q2 to q0 labeled walk => ∈a∈∈ba∈∈

q2 to q3 no such walk

∂*(q2,aba) = {q0,q1,q2} — jatin khachane 1, Oct 7, 2018
@jatin

In question Why q2 is in set notation form in left column , is state q2 and {q2} are same ??

yes.. those are same...

Moreover what you did according to the approach mentioned by peter linz book is also correct. — Shaik Masthan, Dec 3, 2018
@jatin @Shaik

in $\epsilon$ closure

transition on $\epsilon$ and alpbabet comes in any order

Am I right?

I mean in transition, it is no need to mentain transition on 'a' first and then $\epsilon$ transition

right? — srestha, Dec 14, 2018
no mam... first you have to go on epsilon closure then you have to apply a on that set !

if you take alphabet first it will reach Q$_j$ on that you take epsilon closure it is equivalent to taking epsilon closure of Q$_j$ — Shaik Masthan, Dec 14, 2018
Yes...there should a walk from one state to other containing 'a' + any number of epsilon — jatin khachane 1, Dec 14, 2018
@jatin

if a + any number epsilon

then how epsilon comes first?

@Shaik

in epsilon transition , epsilon always comes first?

Is it true for all other cases too? — srestha, Dec 14, 2018
@Shaik

if you take alphabet first it will reach Qj on that you take epsilon closure it is equivalent to taking epsilon closure of Qj

plz elaborate more — srestha, Dec 14, 2018
@Shaik

$\delta ^{*}\left ( Q0,a \right )$ ==> $\epsilon$ closure of Q0 ==> Transition on a==>$\epsilon$ closure of set obtained

Isn't it is same as ==> Set of states reachable from Q0 on seeing any number of $\epsilon$ +'a' + any number of $\epsilon$ — jatin khachane 1, Dec 14, 2018
reachable from Q0 on seeing any number of ϵ +'a' + any number of ϵ

ϵ . 'a' . any number of ϵ — Shaik Masthan, Dec 14, 2018
But peter linz says

1. First compute transition on input

2. Next $\epsilon$ close to the members computed — srestha, Dec 14, 2018
There is a walk between q2 to q3 like this:
$\epsilon a b b$

Am I right? — habedo007, Jan 7, 2020
bhai maja aa gya!! dhanyabad.
glad to see such elegant,nice answer — mohit7891, Jan 11

Aboveallplayer · Answer 1 · 2017-02-14T11:26:15+0000

See all

Show 3 previous comments

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

GATE CSE 2017 Set 2 | Question: 39

How this thing works ..... Refer Peter Linz ...

Please log in or register to add a comment.

Please log in or register to answer this question.

12 Answers

Please log in or register to add a comment.

Please log in or register to add a comment.

Right answer is option C.

Please log in or register to add a comment.

Please log in or register to add a comment.

Related questions

3 3 Comments reply

How this thing works ..... Refer Peter Linz ...

Please log in or register to add a comment.

Please log in or register to answer this question.

12 Answers

9 9 Comments reply

Please log in or register to add a comment.

6 6 Comments reply

Please log in or register to add a comment.

Right answer is option C.

1 1 comment reply

Please log in or register to add a comment.

19 19 Comments reply

Please log in or register to add a comment.

Related questions

3 3 Comments

9 9 Comments

6 6 Comments

1 1 comment

19 19 Comments