Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.
2
votes
1answer
32 views
Do multiple transitions over the input give finite state machines more power?
In the common model of FSA, the automaton reads the input string once, moving from one state to another after reading each letter in the input string. Epsilon transitions allow moving from one state ...
2
votes
1answer
29 views
How does this answer for automata and Hamming distance not lead to inconsistencies?
I had already been given the answer by the TA in class, but I don't understand it. I'm not asking for the answer on a homework problem or anything.
The problem:
The Hamming distance ("distance") of ...
0
votes
0answers
60 views
PDA for $\{x\in\{0,1\}^* : \#_1(x) = 2 \cdot \#_{10}(x)\}$
Let $L_3$ be the language over alphabet $\{0, 1\}$ defined by
$L_3 = \{x : \#_1(x) = 2 \cdot \#_{10}(x)\}$
Here is a design for a PDA that accepts $L_4$. See diagram below, where we use e to donote $\...
1
vote
1answer
23 views
Why is this pushdown automata for some palindromes right?
$B = \{w \in \{0,1\}^* | w^R = w, w \text{ length is odd} \}$
Solution:
For example: $111$ should be accepted
steps are
$q_1 \to q_2$ stack: [$\$$]
$q_2 \to q_2$ stack: $[\$, 1, 1]$ (using up $11$...
1
vote
0answers
17 views
Generalization of formal grammars - production rules with more general functions?
Usually formal grammars have production rules in the format N=tNt where simple concatenation function is used for the expansion of the nonterminal. https://www....
1
vote
1answer
31 views
Proving that L is not regular by showing that $\equiv_L$ has infinite index
Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
1
vote
1answer
37 views
Give a DFSA that accepts $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$ using as few states as possible
Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$.
Using as few states as possible, give a DFSA that accepts $L_1$.
Also give an appropriate state ...
1
vote
2answers
181 views
Minimizing DFA - Dead state elimination
Following is a Question from a competitive exam, it is given that the solution is A but I don’t know why the dead state 4 is not eliminated.Dead states like 4 which has transitions only to itself, ...
-1
votes
1answer
11 views
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
sigma is any alphabet. R is a regular expression.
How can L(RR) even be a subset or equal to L(R)?
-1
votes
0answers
62 views
Need a Book for Theoretical Computer Science for Dummies
I'm having a hard time understanding the first bits of our Theoretical
Computer Science lectures. Although I surpassed the math lectures in
earlier semesters, I can't really figure out most of the ...
0
votes
2answers
39 views
Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages
I'm trying to create a formal algorithm in order to determine whether
two given regular expressions $a$, $a'$ define identical/equal or
unequal languages and if those languages are subsets of each ...
2
votes
2answers
63 views
Prove regular languages are closed under $f(n) = 2^n$ and $ f(n) = n^2$
Suppose $ R $ is a regular language, let $ f(R) = \{ w | $ $ \exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$, prove that $ f(R) $ is regular for $ f(n) = 2^n $ and for $ f(n) = n^2$. I've ...
1
vote
1answer
29 views
The reverse DFA is not working as expected
Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it:
And I reversed the DFA according to this answer (designing a DFA and the reverse of ...
1
vote
3answers
704 views
Loopless NFA equivalent in strength to NFA
For every nondeterministic finite state automata (NFA) that has self-loop(s), there exists an equivalent NFA that does not have any self-loop.
How do I prove this?
0
votes
1answer
30 views
Can this DFA be converted to a regular expression? [duplicate]
I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?
0
votes
0answers
29 views
DFA that accepts those words that a's or b's aren't divisible by 3
I'm have to draw DFA over alphabet $\{a,b\}$, which accepts words where ${a's}$ amount or ${b's}$ amount is not divisible by 3. I don't know how should I start and find out how many states I need.
I ...
1
vote
1answer
22 views
Can a context-senstive gramma contains production rule $cB\rightarrow Bc$?
Some textbook show that the grammar $G=(N,T,P,S)$ below belongs to context-senstive grammars:
S->aSBC
S->abc
cB->Bc
bG->bb
where N={S,B}, T={a,b,c}.
I am confused by the fact that the production ...
2
votes
1answer
1k views
Can someone explain this conclusion for Finite State Machines?
PS It isn't a homework problem..
(But the results seems to be working for me when I checked manually a couple of values of m and n)
Let's say I have two FSM's(calling them A and B)
A is the the ...
0
votes
2answers
50 views
Does the distributive property apply to regular expressions?
Let $(Q,\Sigma,\delta, q_0, F)$ be a finite automaton, does
$$
(q_1a+q_2b)c=q_1ac+q_2bc
$$
hold for any $q_1,q_2\in Q$ and $a,b,c\in \Sigma$?
Here $Sa=\{\delta(q, a)\mid q\in S\}$ and $qa=\{q\}a$ ...
3
votes
2answers
50 views
DFA that accepts any integer $n$ such that $n \bmod 7 =1$
It seems impossible for me to find a pattern for integers $n$ such that $$n \equiv 1 \quad(\bmod 7)$$ in order to construct this DFA.
Is there smart way to do it without a machine which has memory ...
0
votes
1answer
53 views
Can there exist two minimal dfa for same regular language?
As said the answer is pretty simple "no", but that is not what i encountered. Here is the summary : i took a regular language , produced two ways of accepting same language (the ways in my ...
0
votes
1answer
15 views
Simple Definition of a Simple Grammar (with confusing example)
This is the definition of simple grammar that I got from the book "Formal Languages and Automata" by Peter Linz.
There is a homework question that asks for a simple grammar for the language L(aaa*b + ...
1
vote
1answer
22 views
How to address this question of automata proof?
Suppose we allow deterministic automata to read and write from two stacks concurrently, call this a 2-stack DPDA. Prove or disprove the following statements about the set of languages decided by each ...
6
votes
3answers
3k views
Why do pushdown automata use a stack?
I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?
0
votes
2answers
24 views
Is every language over any alphabets is accepted by automata?
The answer is no to what i have learned but i am finding difficulties to absorb it reason being . We say for every language we have a grammar as language without grammar makes no sense even in general ...
0
votes
0answers
42 views
NFA which accepts any $n$ such that $n \bmod 5=0$
I took into account that an integer can't start with a $0$ and that a $0$ could be present somewhere in the middle. Is the below NFA sketch the simplest possible?
0
votes
1answer
82 views
If a language has a regular grammar, is it regular?
If L has a regular grammar, is L always a regular language?
A regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language.
So would ...
1
vote
1answer
37 views
When is the concatenation of a language $L$ with $\Sigma^*$ regular?
I've been looking at questions about the regular concatenation of two languages; one question said that the concatenation of $\{0^n1^n|n\geq 0\}$ and $\Sigma^*$ was regular (over the alphabet $\Sigma =...
1
vote
1answer
32 views
How do I convert the following GNFA to regular expression?
Here is a GNFA I made from an NFA.
I'm unsure how to treat the node of b(a∪b)* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it ...
-1
votes
1answer
40 views
Alan Turing Halting Problem with C code which check how TM works
If we want to write to write a C code, to check if halting problem halts on a given input, how it will be ? I tried this code as shown below but stuck
int main(int argc, char * argv[])
{
<...
0
votes
0answers
25 views
How do I create a regular grammar
I need to create a regular grammar $G$ for the following language: $L(G) = (L_1^* x L_2) \cup L_2$, where $L_1 = \{\mathrm{one}\}$ and $L_2 = \{\mathrm{two}\}$.
Can this be a correct regular grammar:
...
0
votes
1answer
80 views
PDA to accept language with more a's than b's and c's
My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of ...
1
vote
0answers
6 views
Is there anything like equivalence classes in PDA (and more expressive ones, perhaps)?
The motivation for this question is the fact that partitioning DFA into equivalence classes is the mechanism that is used in model testing to generate test cases. However, obviously, DFA cannot ...
6
votes
3answers
2k views
Prove that A** = A*, where A is a language over Σ*
Let $\mathcal A$ be an arbitrary language over $\Sigma^*$
Proof.
To prove, $\mathcal A^{**} = \mathcal A^* $
$\mathcal A^{**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \...
-3
votes
1answer
57 views
Is Countable set always countable?
Why some sets are countable and some are not countable? Say regular set are countable but how (0+1)* will be countable? It is an infinite string, then how it could be a countable set?
How the set of ...
0
votes
2answers
117 views
How does modulus affect the regularity of language?
the question is as follows, further the notation used are standard as used in theory of computation
$$L = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| = 2k\}\,.$$
Beware 'K' is not a fixed integer its ...
1
vote
1answer
21 views
Understanding NFA (nondeterministic finite automaton) with a null transition
I'm reading Computer Science: An Interdisciplinary Approach. It mentioned an NFA (nondeterministic finite automaton) with a null transition, as shown above, recognizes all binary strings that do not ...
0
votes
2answers
65 views
Does there exists a finite automata for the given language?
The question is simple and given as, $alphabets=\{a, b\}$, and language $L$ over them as:
$L = \{w: w \ € \{a, b\}^*, (n(a) - n(b)) \ mod \ 3=1\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of ...
2
votes
1answer
29 views
$a_k$ is $\{L :\exists M$ a pushdown automaton with bounded stack of size $k$ which accept $L\}$ what is the set $\bigcup_1^\infty a_k$?
A related question:
How to prove that a bounded pushdown automaton is regular?
Well I proved that $a_k$ for each $k$ is the set of all the regular language. Thus $\bigcup_1 ^{\infty} a_k = \bigcup_1 ^...
0
votes
0answers
24 views
Proof by induction on “Equivalence of NFA, ε-NFA”
I would appreciate if anyone could help me out with the portion of the proof where I have to construct an NFA from an $\epsilon$-NFA. I do know that doing it otherwise is easy. I am new to the concept ...
2
votes
0answers
27 views
How to know a certain grammar is parse-able
Is it possible to parse all kinds of structured data and give them a semantic meaning? For example, C++ is a really complicated language and I could never imagine a parser would be possible for it.
...
0
votes
1answer
22 views
Why do we take null closure two times while converting from Epsilon-NFA to NFA?
I am studying Theory of Automata. I was studying conversion of Epsilon-NFA to NFA. I had to take null closures of states two times, before and after the specific input.
Could someone explain, what is ...
3
votes
1answer
89 views
Is {<M,w>|M prints more than 300 non-blanks on input w} decidable?
Let
$$ L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$
Is $L_{300}$ decidable?
My intuition is it is decidable because given $M$ and $w$, we need ...
4
votes
1answer
62 views
Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression
Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression?
The way I solved this problem is to first convert the NFA ...
6
votes
2answers
301 views
Find the language an NFA recognizes
For example, I have an NFA $A_n$ with alphabet $\Sigma = \{0, 1\}$.
The language recognized by this NFA is known to be $\{u1v\ |\ u, v \in \Sigma^*, |v| = n − 1\}$.
I was unable to get the ...
1
vote
0answers
19 views
self embedded nonterminal in derivation of a Word
consider this question of finding words with no self embedded nonterminal in their derivation.
The author(cohen) says that If CFG is in CNF then all the words with length greater than 2^p are ...
1
vote
2answers
98 views
How many languages exist over the following alphabets?
(a) We have alphabet $\Sigma=\lbrace 1 \rbrace$, $\Sigma=\lbrace a,b \rbrace$ and (b) also an alphabet with size $k$ and words with length $n$.
For the first two alphabets in (a), we know that there ...
0
votes
1answer
53 views
Is the language $K=\{u \in\{0,1\}| n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$ regular?
For two words $w,v \in\{0,1\}^*$ of equal lenght, let $w+v \in\{0,1,2\}^*$ denote the word in which the $i$-th word is the sum of $i$-th position of $w$ and $v$, as follows: if $w=a_1 \ldots a_n$ and $...
0
votes
1answer
53 views
what are the conditions for two NFAs to be equivalent?
It's a pretty basic question, but I couldn't find an explicit answer in the book which I'm using, also when searching for it - I didn't find a reliable reference.
Correct me if I'm wrong but for two ...
-1
votes
1answer
44 views
Difference between concatenation of two languages and Intersection of two languages
Please also explain in terms of closure of these languages and plot a difference using specific example.
I am interpreted like this and now i am confused.
S1 and S2 are two languages.
"S --> S1. S2 ...
