Tagged Questions

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

22 views

Even String of b's Regular Expression

I was able to find a regular expression over the language {a,b} for all strings containing an even number of b's: $$a^{*}(ba^{*}ba^{*})^{*}$$ However I have two questions pertaining to this regular ...
35 views

26 views

confusion of an example for Powerset construction

I have an example of Powerset construction from the lecture. Powerset construction is applied on automata A1. The result is automata A2. You could see I do Powerset construction myself below the ...
27 views

106 views

The Mathematics of Finite State Automata

I am a final year undergraduate mathematics student preparing to undertake my BSc-HONS project, provisionally titled for the time being, "Finite State Automata and Regular Languages". Having had a ...
46 views

why is the below language a regular set? [closed]

Given a set S={x∣ there is an x-block of 5's in the decimal expansion of π} (Note: x-block is a maximal block of x successive 5's) In the question it is mentioned that there is x-block of ...
17 views

Consider the given regular grammar what are the Myhill-Nerode equivalence classes for the language generated by the grammar?

S → bS | aA | ϵ A → aS | bA A) {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #a(w) is odd} B) {w ∊ (a + b)* | #a(w) is even) and {w ∊ (a + b)* | #b(w) is odd} C){w ∊ (a + b)* | #a(w) = #b(w)...
42 views

30 views

How many states needed for this FSM, and how do I define them?

I want to define states for FSM that gives an output $1$ if and only if $X$ is dividable by $5$ with a residue of 3. where $X$ is the binary number that the machine got until now (Not Including ...
33 views

how to build a PDA for the language of the intesection of PDA and DFA

lets say we got PDA $M=<Q, \Sigma,\Gamma,\delta,q_0,+,F>$ ('+' marks the end of the stack) with $L_1 = L_f(M)$. and we got $A=<P,\Sigma,\delta_1.p_0.F_1>$ with $L_2 = L(A)$. how can I ...