All Questions
19
questions
0
votes
1
answer
87
views
What's the behaviour of $\partial(q, a)=\emptyset$ on NFA?
Given an NFA say $N=(Q,\Sigma, q_0, \partial, F_Q)$, where $\partial: Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal{P}(Q)$. It's confusing about the behavior of say $\partial(q, a)=\emptyset$ for any ...
-1
votes
2
answers
57
views
Why $d^*(q, \epsilon)$ has definition when $d(q, \varepsilon)$ does not in DFA?
I'm reading an online book about DFA and NFA but it confuses me.
Given a DFA say $D=(Q,\Sigma, q_0, \delta, F_Q)$, its transition function is a total function defined on every symbol from a given ...
2
votes
2
answers
224
views
What does it mean when the transition function of a NFA returns an empty set?
Given a NFA, $N = (Q, \Sigma, q_0, \partial, F_Q)$, where $\partial$ is the transition function $Q \times (\Sigma \cup \{ \varepsilon \} ) \to \mathcal{P}(Q) $. So $\partial(q, a)$ returns a set, ...
1
vote
1
answer
220
views
Design a finite state machine that performs the serial addition of three arbitrary binary numbers
Design a finite state machine (by its transition diagram) that performs the serial addition of three arbitrary binary numbers.
For a finite state machine for two binary numbers I got it, but for 3 ...
- 67
0
votes
1
answer
132
views
Deterministic finite automata that accepts words with even number of zeros OR even number of ones
Dear Math Stack Exchange users!
I want to create a deterministic finite automata with max. 5 states, that accepts the language :
$$A:=\{u\in\{0,1\}^*\mid |u|_0\textrm{ mod } 2 \equiv 0\lor|u|_1\textrm{...
1
vote
1
answer
18
views
Is a way to find a single solution for multiple regular expressions?
I have a type of problem that is modeled by non-deterministic finite automata. For my problem, I need to find an input that goes through every unique combination of the non-deterministic split of the ...
- 11
2
votes
1
answer
217
views
Gcd is a Regular Language [closed]
Show that GCD = {z|z = gcd(x,y), where x, y are binary numbers} is a regular
language. [Hint: There is an algorithm that deals with 0s and 1s for this problem.]
- 75
0
votes
1
answer
168
views
Finding regular language and DFA for equation $(2)$
The regular expression for the complement of the language $L = \{a^nb^m \mid n≥4, m≤3\}$ is:
$(λ + a + aa + aaa)b^* + a^*bbbb^* + (a + b)^*ba(a + b)^*$
$(λ + a + aa + aaa)b^* + a^*bbbbb^* + (a + b)^*...
- 4,785
4
votes
1
answer
2k
views
Identify inherently ambiguous languages
Which of the following languages is/are inherently ambiguous languages?
$L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$
$L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$
My attempt:
A ...
- 4,785
1
vote
0
answers
46
views
Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines
The question is:
Let $A$={11,00}.
Find $A^n$ for n=0,1, and 3.
Would i be right in thinking that
$A^0$ = {λ}
$A^1$ = {11,00}
$A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}.
if ...
- 11
0
votes
1
answer
205
views
Induction on String? (automata related)
Honestly, all I know about mathematical induction is as follow:
prove $P(0)$ - base step
for all $n \ge 1$, prove $(P(n − 1) \rightarrow P(n))$ - inductive step
Prove the following claim by ...
- 19
-2
votes
2
answers
115
views
What are good techniques for creating a DFA state diagram given a set of accepted/rejected strings?
I am having trouble coming up with solutions and I think its because I am not approaching these problems in the correct manner even though I understand what a DFA is. For those of you who do well with ...
0
votes
1
answer
3k
views
Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$
Is this a CFL?
$$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$
When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
- 627
1
vote
1
answer
2k
views
Construct a deterministic finite state automaton
Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10.
This is what I drew. Not sure if its correct. State 2 is the final state. Am I missing ...
