Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.
-1
votes
0answers
19 views
How to propose an finite automat for this languages? [closed]
I am struggling the whole afternoon this proposing finite automata for these two languages:
$L_1$ is the set of words in $\{0,1\}^*$ containing an odd number of $0$s and an even number of $1$s.
...
2
votes
1answer
31 views
Cartesian construction of PDA and DFA
How would I go about using Cartesian construction to find the intersection between a PDA and a DFA?
Is there another term for Cartesian construction? Would it be similar to the procedure for finding ...
0
votes
1answer
35 views
Simple FSM question
Considering this FSM:
Can someone explain me why the grammar is not:
$S \rightarrow aA$
$A \rightarrow aA \mid bB \mid \varepsilon$
$B \rightarrow bB \mid \varepsilon$
Why does A not have a ...
6
votes
4answers
208 views
Can an FSA count?
This may be a silly question. It seem clear that an FSA, since it is finite, can only count the number of symbols in its input string up to a number bounded by the number of its states. But now ...
1
vote
1answer
41 views
Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable?
I have an exam coming up and I need help with the following homework:
Given an NFA $A$ and a regular expression $B$, consider the problem of determining if $L(A) = L(B)$. Is this decidable? Prove ...
4
votes
2answers
96 views
Why is the following language not context-free?
$L = \{a^n b^m | m \not= n^2 \}$
I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.
Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
5
votes
3answers
99 views
Can a Turing Machine decide if a regular expression matches all strings of exactly some length $l \geq 1$?
Earlier I asked the question: Can a Turing Machine decide if an NFA accepts a string of prime length?. The answer introduced me to Parikh's theorem, which I've been reading about. The concept of ...
10
votes
1answer
169 views
Can a Turing Machine decide if an NFA accepts a string of prime length?
I want to know if the following problem is decidable:
Instance: An NFA A with n states
Question: Does there exist some prime number p such that A accepts some string of length p.
My belief is that ...
6
votes
1answer
102 views
Difference between the languages accepted by two DFAs with different initial state/accepting states?
Recently, I asked a question on Math SE. No response yet. This question is related to that question, but more technical details toward computer science.
Given two DFAs $A = (Q, \Sigma, \delta, q_1, ...
4
votes
1answer
55 views
A procedure for Topological sort, proof for its correctness
Definition: A preserved invariant of a state machine is a predicate, $P$, on
states, such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$ for some state, $r$,
then $P(r)$ holds.
...
1
vote
1answer
74 views
Union of two automata
I need to find a minimal DFA given the following information:
$ \{a^nb : n\geq 0\} \cup \{b^na: n \geq 1\}$
Now, maybe I'm not seeing this properly, but I don't see how this is possible: the ...
-3
votes
2answers
69 views
Build a FA that accepts the language of all strings of length 4 or more such that the next-to-last letter [closed]
Can anyone solve this?
"Build an FA that accepts the language of all strings of length 4 or more such that the next-to-last letter is equal to the second letter of the input string."
3
votes
1answer
49 views
Difference between pattern matching and pattern searching in terms of DFA/Regex
E.g.
Matching Problem The DFA of regex good is like a chain.
...
3
votes
1answer
81 views
Can we say anything about the complement of a regular language?
Given a regular language $L$, can we say anything about its complement $\overline L$? One thing that is trivial to say is that the DFA's for both languages are equal in size as complementing the ...
3
votes
2answers
106 views
What is the difference between finite automata and finite state machines?
I have used FSM in Digital sequential Circuit designs. But I am unfamiliar with Finite Automata. Can somebody help me in understanding 'basic' difference between the two ?
