# Questions tagged [finite-state-machine]

For questions about finite state machine, which is a mathematical model of computation.

59 questions
Filter by
Sorted by
Tagged with
39 views

### Prove\Disprove: If $L_1$ is not a CFL, and $L_2$ is finite, then $L_1 \cup L_2$ is not a CFL.

I am getting ready for finals, and encountered this question in a past assignment. I haven't proved this then and I don't understand how I can prove it now. Prove\Disprove: If $L_1$ is not a Context-...
23 views

### How do I convert the following NFA to a DFA?

From my textbook, I am trying to convert the above NFA to a DFA (no solution provided). I went through the steps to convert it and ended up with the following DFA solution: At first glance, I thought ...
19 views

### Finite State Machines: Can a state diagram have more than one self-loop?

According to Schaum's Outlines, the state diagrams of Finite State Machines are labelled directed graphs. Now, it is entirely possible that the resultant state after transition returns to itself more ...
22 views

### If L is regular, then $L \setminus \{ \epsilon \}$ is regular.

I need to show that if $L$ is regular language, then $L \setminus \{ \epsilon \}$. I was thinking: If $L$ contains $\epsilon$, then in the FSA the start state is a final state. But by making the start ...
50 views

### Is Shuffling of a regular language regular too?

If $A$ be regular language, How we can prove that $A^{'}$ is regular too? $A^{'} = \{a_{2}a_{1}a_{4}a_{3} ... a_{2n}a_{2n-1} \mid a_{1}a_{2}a_{3}...a_{2n} \in A\}$ Is there any way to prove that even/...
24 views

### Pumping Lemma to prove language not regular, formatting $x$

I need help with a question/verification I'm even thinking about it correctly. I'm trying to use the PL to prove $L$ is not regular. $L = \{\{a,b,c\}^* \mid |a| < |b| \wedge |a| < |c|\}$. This ...
78 views

15 views

### Minimize the finite state machine given by the following state table

Minimize the finite state machine given by the following state table
24 views

### Calculating a transition probability in FSM

I have a Finite State Machine represented in following form: ...
67 views

### Finite State Automata

it's been a while since I've done FSA's so I'm a little rusty, bear with me. I'm creating an FSA to parse Integer and Decimal tokens for a class. The two tokens have the regex Integer: $0|[1-9][0-9]^*$...
48 views

### Non-linear recurrence relation with Kronecker delta

I am studying a game in number theory and I have come across some non-linear (coupled) recurrence relations which involve what I've been referring to as Kronecker deltas (or unit sample functions). An ...
12 views

### Are the following conversions from DFAs to GNFAs correct?

This machine (a) should accept all strings that start with a 1 and end with a 0. This machine (b) should accept all strings that contain three or more 1s. This machine (c) should accept all strings ...
93 views

### Floyd Invariant Principle on a deck of cards [closed]

The below problem has been taken from Mathematics for Computer Science (MIT Opencourseware https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-...
81 views

245 views

### First Order Logic knowledge base problem

I would like to present in the predicate logic the knowledge base and then check if the one provided formula is satisfied using the defined knowledgebase. I am trying to do this using SPASS prover, ...
882 views

### Creating a deterministic Finite state machine that accepts even 1s parity

Ive been working on this project for over a week now and its coming due soon, and im in no way going to finish it soon. the project is essentially where we have been assigned 3 "Codes" which form a ...