Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...