Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [finite-automata]

235 questions
4
votes
3 answers

Epsilon and phi in automata

If $L_1 = Ø$, I read that $L_1^\ast$ is $\{\varepsilon\}$. Why is this so? I am unable to understand this. Can someone please explain? I understand that $Ø$ is an empty string while $\varepsilon$ allows us to make transitions without symbols. But,…
Venkatesh Vinayakarao
  • 93
3
votes
2 answers

Finding a language expressed by an automaton

I'm having trouble trying to find a language expressed by this automation. I have constructed a next-state table to help me understand better. From my understanding, any string that starts with 0 takes my automaton A to an accepting state but what…
ekeith
  • 169
3
votes
1 answer

Can a finite state machine contain an unreachable state?

If a finite state machine is formally defined with a set of states $\{q_0, q_1, q_2\}$, where $q_0$ is the start state, is it a valid machine if there is no path from $q_0$ to $q_1$ and no path from $q_2$ to $q_1$? In other words, there is no way to…
Solomon
  • 33
2
votes
1 answer

Is this NFA right?

Create a NFA for the following language $$\{w \mid w \text{ contains an even number of $0$s, or contains exactly two $1$s }\} \enspace.$$ Do it with six states: My NFA However, I think I made it too hard and the following one is far simpler. I…
TheMathNoob
  • 2,011
2
votes
1 answer

FA that accepts odd number of $b$ and even number of $a$

I'm having trouble understanding the wording of one of my homework questions. Since this question appears early in the chapter, I have a feeling that I'm misinterpreting it. Give a finite automaton that that accepts the following language: The…
Liam
  • 293
1
vote
0 answers

How to evaluate this transition function when converting from PDA to CFG?

I'm trying to convert a PDA to CFG. What is the production in the below transition. I'm stuck here. $$δ(q_1,ε,Z_0)=(q_2,Z_0)$$ Also pls state detailed rules or rules for specific situations as the general rules doesnt seem to answer what to do in…
user103292
  • 91
1
vote
2 answers

Transition function of a NFA

For a DFA, the definition of the transition function for a string is: $$ \widehat{\delta}:Q\times\Sigma^\star\to Q $$ The first part (before the arrow) defines all combinations of all strings with all states by using the cartesian product. Each one…
Ruben23630
  • 83
1
vote
0 answers

How to Change an FA to a Push Down Automata

I am supposed to draw a Push Down Automata that would function the way a normal calculator would which accepts only correct mathematic expressions. I was given an FA but i dont know how to change it to a PDA, so please give me a crash course on PDA…
Jack Sindler
  • 21
1
vote
1 answer

Build a DFA that accepts $L(M_1)-l(M_2)$

I am unsure as how to do this because the inputs accepted on both are $\{0, 1\}$ and the states are all different, so I am unsure which sets I am subtracting. Like I said, if the languages are equal and I subtracted, wouldn't I get no acceptable…
matttm
  • 92
1
vote
1 answer

Exam Question - language recognizition

I was at the Math-exam yesterday, and I am a bit unsure, if i solved a math problem correctly. The question was something like this: Draw a automata that recognise the following language: $$ L = \{w : (0 | 1)^* \text{and } w \text{ ends with }…
TheFermat
  • 365
1
vote
1 answer

Finite-State Automaton

I have been given the following assignment in a discrete mathematics course: A simplified telephone switching system allows the following strings as legal telephone numbers: a. a string of seven digits in which neither of the first two digits are…
bacon
  • 13
0
votes
1 answer

Construction of nfa consisting of accepted state in outcome for given string not part of language-

Can in set of possible final states reachable from initial state in nfa can consist of accepted state if input string is not a part of our given language? Here is the example, I want to discuss about- Design a nfa for a language that accepts all…
Aman Khandelwal
  • 3
0
votes
0 answers

Contruct the Deterministic Finite Automata

Give a DFA for $\Sigma = \{0, 1, 2, 3, 4\}$ that recognizes strings over the alphabet $0, 1, 2, 3, 4$ which are integers with a digit sum of $6$ and may have leading zeros. For example, $1230$ should be in the language since $1 + 2 + 0 + 3 = 6$, and…
Tinkle Tin
  • 1
0
votes
1 answer

Table-filling method for DFA minimization with non-binary alphabet

Hi! Using table-filling method, how do I prove that states A and B are distinguishable? A,C and B,C initially marked pairs are obviously allright, but then when I look at A,B , there is no symbol s in the alphabet {1,2,3} that I can use to analyze…
Boris-Barboris
  • 23
0
votes
1 answer

Non deterministic finite automata intuition

I'd believe that the theorem is true, simply because you can draw an NFA representation of a kleene star. However I'm not sure about what the proof means, with regards to the statement that "i and j are distinct and qi = qj". It looks to me like…
pajkatt
  • 373
1
2