menu
search
Log In
Quick search syntax
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

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Theory of computation dfa construction

0 votes
108 views
$\Large L = \left \{ a^{m^n} | n \geq 1, m > n \right \}$

What is the Minimum no.of states in a DFA which accept this language
in Theory of Computation
edited by 108 views
0

did you get what are the stings of L ?

if you get it, then 90% of your problem solved.

check this https://gateoverflow.in/242006/regular-language-identification

https://gateoverflow.in/242910/regular-grammar

1 Answer

0 votes
 
Best answer
here consider n=1 permanently and m=2,3,4,5,............ so it is set of all strings of length atleast 2....

selected by
0
Not length ...no.of a's precisely...dfa should have 3 states then?
← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

1 vote
1 answer
1
470 views
Grammar to DFA Construction
For the given Grammar S->aA|bB A->bC|aS B->aC|bS C->aB|bA Construct DFA I am getting confused in understanding how to take the final state.
For the given Grammar S->aA|bB A->bC|aS B->aC|bS C->aB|bA Construct DFA I am getting confused in understanding how to take the final state.
asked Oct 13, 2018 in Theory of Computation sripo 470 views
2 votes
3 answers
2
592 views
Ace Test Series: Theory Of Computation - Finite Automata
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language? $4$ $16$ $20$ $24$
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language? $4$ $16$ $20$ $24$
asked May 22, 2019 in Theory of Computation Hirak 592 views
0 votes
1 answer
3
1.1k views
Number of states in DFA divisible by 8
Number of states for DFA which is divisble by 8 , I mostly try to identify by using number of distinct states. In this case , it would be 8 ; but minimized dfa would be less ? I read somewhere , the unique states sould be 4 and so ... but is this right ? And can someone explain , what is meant by unique states ? Do we have fixed formula for such problems ?
Number of states for DFA which is divisble by 8 , I mostly try to identify by using number of distinct states. In this case , it would be 8 ; but minimized dfa would be less ? I read somewhere , the unique states sould be 4 and so minimum states are 4. Can't ... exceprt now , but is this right ? And can someone explain , what is meant by unique states ? Do we have fixed formula for such problems ?
asked Dec 7, 2016 in Theory of Computation vishal8492 1.1k views
1 vote
2 answers
4
511 views
Number of DFA ?
Let $q_0$ and $q_1$ be two states, with $q_0$ always being the initial state. Let the alphabet be $\{a, b\}$. Then, the possible number of DFA's with only these two states $q_0$ and $q_1$ is? 32 64 80 120
Let $q_0$ and $q_1$ be two states, with $q_0$ always being the initial state. Let the alphabet be $\{a, b\}$. Then, the possible number of DFA's with only these two states $q_0$ and $q_1$ is? 32 64 80 120
asked Nov 22, 2015 in Theory of Computation prathams 511 views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...