1
vote
2answers
42 views

Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Draw a finite state machine which will accept the regular expression: $(a^2)^* + (b^3)^*$ In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about ...
1
vote
1answer
33 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
2answers
21 views

Convert NFA with only accepting states to regular expression?

Suppose you wanted to find a Regular Expression that defines the language accepted by the folowing Finite State Automaton. Where S1 and S2 are both accepting states. How would I go on doing this?
3
votes
3answers
62 views

Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
0
votes
2answers
75 views

What is the language generated by G and how to draw the finite state automaton that recognizes this language?

G = (V, T, S, P) V = (0, 1, A, B, S) T = {0, 1} S is start S -> 0A S -> 1A A -> 0B B -> 1A B -> 1 For the drawing, I am confused about the last ...
0
votes
1answer
141 views

Grammar Construction from Given Language!

Just a fast question! I have this language L(G) = { z^n * x^2n with n>=1 } What is the grammar ? I think it should rather be: ...
1
vote
1answer
54 views

Languages and Grammar (Finding a language)

I have a trivial question (that I have actually solved, hopefully) although I am a bit curious if my result is alright. We have $N= \{S , C ,D\}$, $T=\{c, d\}$ and $P = \{S \to Dc, D \to Dd, D \to ...
2
votes
1answer
209 views

Verification: DFA/NFA that accepts all strings over $\{0,1\}$ with exactly one block of $00$

I am trying to design a DFA or NFA that accepts all strings over $\Sigma = \{0,1\}$ in which the block $00$ appears only once. Here is what I've tried. Can you verify that this accepts all string ...
0
votes
0answers
247 views

Turing Machine question, this is NOT HW

I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
1
vote
2answers
706 views

Concatenation of 2 finite Automata

I have some problems understanding the algorithm of concatenation of two NFAs. For example: How to concatenate A1 and A2? A1: ...
1
vote
1answer
236 views

Finite state machine to report when the last 4 inputs were 1011

Suppose you want to construct an FSM containing one input and one output. Consider the example: The machine should assert the input (set to 1) when the last four bits taken in as input match the ...
0
votes
1answer
219 views

How do I write this formally?

For every number N in a sequence of numbers it is true that each odd N is followed by 0 or more other numbers (not including 0) then the number N+1. How do I write this formally? This is my attempt ...
7
votes
2answers
398 views

A magic trick with synchronizing words

See the following magic trick. http://www.speedyadverts.com/SAEntertainment/html/realmagic4.html Spoiler Alert Believe it or not, the lady didn't really read your mind; she is not even a real lady ...
2
votes
1answer
380 views

Understanding and using the transfer-matrix-method

Let $G = (V,E,\Phi)$ be a weighted directed graph and $\mathcal{W}' : E \rightarrow \mathbb{C}$ the weighting. Let additionally $m = \# V$, $E_m$ the $m \times m$ identity matrix. Let $v,w \in ...