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

learn more… | top users | synonyms

0
votes
2answers
71 views

What is the difference between the automatas for the regular expressions (a + b)* and (a* + b*)?

I know that the automaton for the regular expression (a + b)* will just have one state, where the initial state = the accepting state and there is one edge going into that state labelled a,b. Sorry, ...
0
votes
0answers
94 views

A question about the language of a non-deterministic FSA defined by a non-deterministic FSA with epsilon moves

I have tried to solve the following problem and my claims were marked as wrong, I would appreciate it if someone could point out my mistake Let $A=(Q,\Sigma,q_{o},\delta,F)$ be a finite state ...
0
votes
1answer
102 views

Finding if two machines can be equivalent

I have this problem: Consider the following machines M1 and M2. M1 has initial state A and the initial state of M2 is unspecified. Can the machines be made equivalent by the correct choice of ...
0
votes
0answers
35 views

Proof two FSM are k-equivalent [duplicate]

Possible Duplicate: Confusion related to state equivalence of finite state machines Show that p is k-equivalent to q, if and only if that any x belongs to S*, |x|=k, g(p,x)=g(q,x) Any ...
0
votes
2answers
361 views

DFA and NFA equivalent language

I'm asked to build a DFA A and NFA B such that L(D) = L(N) with some specific conditions. I'm not asking for solutions or answers; I just wanted to make sure I have the right method to attack this ...
0
votes
0answers
270 views

Deterministic Finite Automata: State Diagram Notation

Refer to the paper Radu Grosu, "Finite Automata as Time Invariant Linear Systems - Observability, Reachability and More". I have a problem understanding the state transition diagram of DMA $M_1$ in ...
-1
votes
1answer
83 views

pumping lemma for regular languages and DFA with k states

The Formal statement of the pumping lemma for regular languages: Let $L$ be a regular language. Then there exists an integer $p \ge 1$ depending only on $L$ such that every string $w$ in $L$ of ...
-1
votes
1answer
77 views

How does this language accept all palindromes with the alphabet {a,b}? [closed]

$L = \{w \in \{a,b\}^{*}$ such that $w = w^R\}$ It only says that w is the reverse of w. $L = \{ww^R \in \{a,b\}^{*}$ }$ this one says it accepts all palindromes, but the other one doesn't.
-1
votes
2answers
78 views

Is λ={λ} true or not

I know that λ={λ} is true i want to know How can i prove that λ={λ} is true or not? Thanks in advance.
-1
votes
1answer
50 views

Finding the CFG (Context Free Grammar) of a language

Can we write a CFG (Context Free Grammar) for the set of all non-empty string whose length are multiple of 3 on the alphabet $ \Sigma = \{A,R,G,C\} $
-1
votes
1answer
160 views

Decidability/Undecidability Question

Could someone please help me with this question? I'm really having a hard time understanding reductions and decidability. Prove that the language $$L = \{\langle M,N \rangle \mid M,N\text{ are Turing ...
-1
votes
1answer
25 views

transition graph that accepts only Λ and language a*

I am trying to have a transition graph that accepts only Λ and also one that accepts language a* ...is this ok ??? transition graph that accepts only Λ transition graph that accepts language a*
-1
votes
1answer
21 views

disproving union of infinitely many regular languages

I want to disprove the following statement: "if $L$ is the union of infinitely many regular languages, then $L$ is guaranteed to be a regular language." I don't know where to start. Any hint will be ...
-1
votes
2answers
80 views

Find a CFG for L = { a^nb^m : n != m }

This question is upcoming for my midterm and I can't figure it out. My professor broke it down in two statements (n>m) and(m>n) and left us at that. Find a context free grammar for $L = \{ a^n b^m : ...
-2
votes
0answers
37 views

Pumping Lemma & Regular Language

For each regular language L, we have an integer k such that: ...