Recent questions tagged finite-automata / GATE Overflow for GATE CSE

1 votes

1 answer

931

Why a^n / n is odd (even) is regular Language ?
How could we construct a FA by finding out a pattern in this language if we take n is odd then we consider n=1 ,3 ,5 ,7 (here string is in AP so we would be able to find out FA) it is okay but it it not said that we should ... but now there is no pattern now how can we construct a FA ).... can someone explain this ? Assume same for if n is even.

How could we construct a FA by finding out a pattern in this language if we take n is odd then we consider n=1 ,3 ,5 ,7 (here string is in AP so we would be able to find...

shekhar chauhan

1.9k views

shekhar chauhan asked May 10, 2016

0 votes

0 answers

932

Problem in Understanding the DFA, Need Help
I am reading Hopcroft Ullman - Automata Theory(2nd Edition). In page Number 65 (Red Underline part in the given Image); I understand when i=1 but unable to understand when i>1 then how the Accepting and Non-accepting State are same. My ... Accepting and Non-Accepting; it may be Accepting and Non-Accepting ". Please help me............ Thanks

I am reading Hopcroft Ullman - Automata Theory(2nd Edition).In page Number 65 (Red Underline part in the given Image); I understand when i=1 but unable to understand whe...

Bhaskar Singh

305 views

Bhaskar Singh asked Apr 24, 2016

27 votes

3 answers

933

GATE CSE 2007 | Question: 75
Consider the following Finite State Automaton: The minimum state automaton equivalent to the above FSA has the following number of states: $1$ $2$ $3$ $4$

Consider the following Finite State Automaton:The minimum state automaton equivalent to the above FSA has the following number of states:$1$$2$$3$$4$

go_editor

8.5k views

go_editor asked Apr 23, 2016

0 votes

1 answer

934

MadeEasy Test Series: Theory Of Computation - Finite Automata

Sourabh Kumar

321 views

Sourabh Kumar asked Apr 22, 2016

2 votes

2 answers

935

is a*b* is a regular expression ?
if yes then what is the difference b/w a*b* and a^n b^n ?if yes what is that ? if nothing then why a^n b^n is not a regular Language ? Forgive me if this is a stupid question .But as a non cs student i don't know what is going on in TOC .

if yes then what is the difference b/w a*b* and a^n b^n ?if yes what is that ? if nothing then why a^n b^n is not a regular Language ?Forgive me if this is a stupid quest...

shekhar chauhan

857 views

shekhar chauhan asked Apr 22, 2016

1 votes

2 answers

936

What language does this FA represent ? And what is the regular expression for this FA ?

shekhar chauhan

1.1k views

shekhar chauhan asked Apr 21, 2016

1 votes

1 answer

937

Model this toy by a Finite Automata

Bhaskar Singh

2.6k views

Bhaskar Singh asked Apr 15, 2016

19 votes

3 answers

938

How to construct an automata with even number of a's and odd number of b's?
The alphabets are a and b. Construct a DFA

The alphabets are a and b.Construct a DFA

Gourab_Classic

109k views

Gourab_Classic asked Mar 14, 2016

79 votes

3 answers

939

GATE CSE 2016 Set 2 | Question: 42
Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT? Only I is true Only II is true Both I and II are true Both I and II are false

Consider the following two statements:If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$.There exists a regular languag...

Akash Kanase

25.6k views

Akash Kanase asked Feb 12, 2016

38 votes

5 answers

940

GATE CSE 2016 Set 2 | Question: 16
The number of states in the minimum sized DFA that accepts the language defined by the regular expression. $(0+1)^{*} (0+1) (0+1)^{*}$ is ________.

The number of states in the minimum sized DFA that accepts the language defined by the regular expression.$(0+1)^{*} (0+1) (0+1)^{*}$is ________.

Akash Kanase

15.8k views

Akash Kanase asked Feb 12, 2016

1 votes

1 answer

941

Regular expression for all strings starts with ab and ends with bba is.
Regular expression for all strings starts with ab and ends with bba is. a) aba*b*bba b) ab(ab)*bba c) ab(a+b)*bba d) All of the mentioned Doubt: starting with 'ab' and ending with 'bba', so 'abba' should also be accepted right?

Regular expression for all strings starts with ab and ends with bba is.a) aba*b*bbab) ab(ab)*bbac) ab(a+b)*bbad) All of the mentionedDoubt: starting with 'ab' and ending ...

Purple

14.8k views

Purple asked Jan 28, 2016

0 votes

1 answer

942

Finding minimum states in FA.
If it is asked for minimum states required in FA for some language, we can have both NFA and DFA, and NFA has lesser number of states but many books write that consider DFA as default. What to take into consideration in such case?NFA or DFA?

If it is asked for minimum states required in FA for some language, we can have both NFA and DFA, and NFA has lesser number of states but many books write that consider D...

parthsl

707 views

parthsl asked Jan 27, 2016

0 votes

0 answers

943

Minimization of dfa
Do we have any shortcut for minimization of dfa

Do we have any shortcut for minimization of dfa

Jose Kj

1.1k views

Jose Kj asked Jan 24, 2016

0 votes

5 answers

944

MadeEasy Test Series: Theory Of Computation - Finite Automata
Let L = {(aP)*⎪P is a prime number} and Σ={a}. The minimum number of states in NFA that accepts the language L are ________. i don't think it is even a regular language. then how can NFA be generated?

Let L = {(aP)*⎪P is a prime number} and Σ={a}. The minimum number of states in NFA that accepts the language L are ________.i don't think it is even a regular language...

khushtak

2.2k views

khushtak asked Jan 21, 2016

1 votes

0 answers

945

NFA intersection
How do I construct the intersection of two NFAs? Do I need to follow the same cross product method like the DFAs? If so, then how do I handle the epsilon transitions? Please support your answer with an example Thanks in advance!

How do I construct the intersection of two NFAs? Do I need to follow the same cross product method like the DFAs? If so, then how do I handle the epsilon transitions?Plea...

chat28

909 views

chat28 asked Jan 16, 2016

1 votes

1 answer

946

TestBook Test Series: Theory Of Computation - Finite Automata
Only way NFA of 6 states can be reduced to DFA of one state if all remaining 5 states of NFA are useless (Unreachable etc) & THere are no Dead State. In any normal NFA without useless states, I think we need at least same no ... states. !) I do not agree to 1 , as it means that all states other than start state in NFA was useless.

Only way NFA of 6 states can be reduced to DFA of one state if all remaining 5 states of NFA are useless (Unreachable etc) & THere are no Dead State. In any normal NFA wi...

Akash Kanase

689 views

Akash Kanase asked Jan 15, 2016

2 votes

2 answers

947

Minimum number of states in the DFA
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$ I draw the following DFA The minimum number of states is 4. The answer given is 8. How is it possible? Please explain.

What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$I draw the following DFA The minimum number of states is 4. The answer giv...

Utk

16.2k views

Utk asked Jan 13, 2016

11 votes

1 answer

948

Identify language
Consider the sets over $\left\{a,b\right\}$ $S_1=\left\{a,ab\right\};$ $S_2=\left\{b,ba\right\};$ $S_3=\left\{a^nb^{2n}\right\}\cup \left\{a^{2n}b^n\right\};$ $S_4=\left\{ww^R|w\in(a,b)^*\right\};$ ... prefix property. But, why cant they be accepted by dfa (where we dont check prefix property satisfaction). If pda was given then they would have been right, I guess.

Consider the sets over $\left\{a,b\right\}$$S_1=\left\{a,ab\right\};$$S_2=\left\{b,ba\right\};$$S_3=\left\{a^nb^{2n}\right\}\cup \left\{a^{2n}b^n\right\};$$S_4=\left\{ww^...

Tushar Shinde

2.8k views

Tushar Shinde asked Jan 12, 2016

2 votes

1 answer

949

∈-NFA TO NFA
Construct an eqv. NFA for the given ∈-NFA Is this eqv. Nfa correct?? Or this one Why is thr transition between q0 to q1 of 0,1 ?

Construct an eqv. NFA for the given ∈-NFAIs this eqv. Nfa correct??Or this oneWhy is thr transition between q0 to q1 of 0,1 ?

khushtak

3.3k views

khushtak asked Jan 11, 2016

0 votes

0 answers

950

Dfa
Construct the minimal dfa that accept all binary numbers which have congruent to 2mod4 Can't we eliminate state q3? as q1 and q3 hav same inputs and output transition. I think it is same as a language having strings ending with 10. Right na?

Construct the minimal dfa that accept all binary numbers which have congruent to 2mod4Can't we eliminate state q3?as q1 and q3 hav same inputs and output transition.I thi...

khushtak

401 views

khushtak asked Jan 11, 2016

2 votes

1 answer

951

Dfa identify the language accepted by the following dfa
Accepting language is1- [(1*0)*01*]*0* Or 2- (1*0)*0]*0* any of these is correct??

Accepting language is1- [(1*0)*01*]*0* Or 2- (1*0)*0]*0* any of these is correct??

khushtak

1.2k views

khushtak asked Jan 10, 2016

1 votes

1 answer

952

Language and its compliment
Given $(L')^* = (L^*)' where ' is complement operation. $L$ is ? $ \phi, \{\epsilon \}$ and $ \Sigma^*$ $\{\epsilon \}$ and $\Sigma^*$ $ \phi $ and $\{\epsilon \} $ $L$ is not any of $\phi, \{\ ... $\Sigma^*$ Please someone explain the meaning of ∅ and comp(∅) also. This question got me confused over the meaning of ∈ also.

Given $(L')^* = (L^*)' where ' is complement operation.$L$ is ?$ \phi, \{\epsilon \}$ and $ \Sigma^*$$\{\epsilon \}$ and $\Sigma^*$$ \phi $ and $\{\epsilon \} $$L$ is no...

Utk

568 views

Utk asked Jan 4, 2016

2 votes

0 answers

953

For a length of string n,how many transactions will be there for acceptance of the string?
For a length of string n,how many transactions will be there for acceptance of the string? O(n) O(n^2) O(nlogn) O(n^3)

For a length of string n,how many transactions will be there for acceptance of the string?O(n)O(n^2)O(nlogn)O(n^3)

nilamd

406 views

nilamd asked Dec 24, 2015

2 votes

1 answer

954

MadeEasy Test Series: Theory of Computation- Finite Automata
Q.51 Consider the finite automaton is the following figure. What is the number of state to accept same language by DFA for above NFA (need not minimum)? 7 9 11 16 I think here minimum state required is 8. So 9 is correct answer !

Q.51Consider the finite automaton is the following figure.What is the number of state to accept same language by DFA for above NFA (need not minimum)?791116I think here m...

Akash Kanase

588 views

Akash Kanase asked Dec 19, 2015

1 votes

1 answer

955

TOC question from virtual gate
Given answer: A Please explain

Given answer: APlease explain

shikharV

829 views

shikharV asked Nov 24, 2015

2 votes

2 answers

956

What is the Regular Expression for
The regular expression for the language recognized by the following Finite State Automaton is? $0^* \mid 0^* 1^+$ $0^* \mid 11^*$ $0^* \mid 0^* 1^+ \mid 0^* 1^+ (0+1)^*$ None of these.

The regular expression for the language recognized by the following Finite State Automaton is?$0^* \mid 0^* 1^+$$0^* \mid 11^*$$0^* \mid 0^* 1^+ \mid 0^* 1^+ (0+1)^*$None...

sabir

1.6k views

sabir asked Nov 17, 2015

2 votes

1 answer

957

toc
The number of states in a minimal finite automata accepting the empty set is_________.

The number of states in a minimal finite automata accepting the empty set is_________.

Nisha kumari

1.2k views

Nisha kumari asked Nov 9, 2015

1 votes

1 answer

958

toc
Consider $\text{dfa}$, $\text{nfa}$ & $\varepsilon$ -$\text{nfa}$ accepting the same language. Choose the correct statement? All three models always have the same number of states. The minimal $\text{dfa}$ for all three machines is unique The $\text{nfa}$ model always has more number of states than the $\text{dfa}$ The $\varepsilon$- $\text{nfa}$ always has the maximum number of states

Consider $\text{dfa}$, $\text{nfa}$ & $\varepsilon$ -$\text{nfa}$ accepting the same language.Choose the correct statement?All three models always have the same number of...

focus _GATE

461 views

focus _GATE asked Nov 5, 2015

2 votes

1 answer

959

toc
There exist algorithms to decide if a finite automata accepts the empty set. accepts a finite number of strings. accepts an infinite number of strings. all of the above.

There exist algorithms to decide if a finite automata accepts the empty set. accepts a finite number of strings. accepts an infinite number of strings. all of...

focus _GATE

563 views

focus _GATE asked Nov 5, 2015

3 votes

1 answer

960

Draw NFA.
1) Design an NFA with no more than $5$ states for: $L_1 = \left \{aba b^n \mid n \geq 0 \right \} \cup \left \{ ab a^n \mid n\geq 0 \right \}$ 2) Design an NFA with $3$ ... $4$ states for: $L_3= \left \{ a^n \mid n\geq 0 \right \} \cup \left \{b^n a \mid n \geq 1 \right \}$

1) Design an NFA with no more than $5$ states for: $$L_1 = \left \{aba b^n \mid n \geq 0 \right \} \cup \left \{ ab a^n \mid n\geq 0 \right \}$$2) Design an NFA with $3$ ...

Pooja Palod

719 views

Pooja Palod asked Oct 28, 2015

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