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
0answers
20 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. ...
-1
votes
0answers
19 views

How can I prove that the language is regular for the following: {w|w contains an equal number of occurrences of the substrings 01 and 10} [duplicate]

I was able to come up with both the DFA and NFA, but I have no idea how to prove that the language is regular. Any help would be great!
0
votes
1answer
16 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
83 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
41 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
277 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
14 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
1answer
65 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
0answers
20 views

Relationship b/w closure and decidability property

Is there a relationship b/w closure and decidability property for a language?
0
votes
1answer
37 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
48 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
27 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 ...
0
votes
1answer
36 views

Finite state automaton for the reverse of the language, and multiple starting states

I am studying about Finite State Automaton, and I found that the when reversing a language (i.e., transforming $L$ to $L^R$), I have to add new start state. Why is that? Also, can a Finite State ...
0
votes
1answer
49 views

Is there a proof that shows why DFAs can't be used to show the concatenation of two regular languages?

Sipser goes on to show that regular languages are closed under concatenation using NFAs. His proofs typically use NFAs to prove closure under the operations. Is there an alternative proof that goes ...
1
vote
1answer
21 views

Language equivalent states in a deterministic parity automaton

Given a deterministic parity automaton $\mathcal{A}$ with state set $Q$ and a state $q \in Q$, we denote with $\mathcal{A}_q$ the same automaton with initial state $q$. Two states $p$ and $q$ are ...
3
votes
2answers
32 views

Question about mapping reducibility

I am working on an assignment where one of the sub questions is: Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \...
2
votes
1answer
42 views

Context formal language recognizing even number of 0's and odd number of 1's

I have an assignment, it's asked to write a context free grammar recognising the language $L=\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\}$, over the alphabet $\{...
0
votes
1answer
46 views

Does a pushdown automata exists for the following language?

I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another ...
1
vote
2answers
124 views

Algorithm for printing all accepted strings (to an upper bound if infinite amount) from a given DFA

As the title states I'm trying to write an algorithm that generates accepted strings to an upper bound from a given DFA. It should not generate more strings than the upper bound n if it contains ...
1
vote
2answers
33 views

Understanding $\epsilon$ transitions on NFA

I can't understand why $\epsilon$ is accepted. I thought if $\epsilon$ is inputed then it would go from $q_1$ to $q_3$. $a$ is also accepted, but I though if $a$ is inputed then then the NFA would die,...
4
votes
1answer
51 views

Is the symmetric difference of a non regular language L and a finite language f non regular?

The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$. Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric ...
0
votes
1answer
46 views

Define a grammar to emmulate chess rules

Is it possible to define a 《chess language》: language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}? I looked online but I cannot find a ...
0
votes
1answer
36 views

Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$ [closed]

How can I express this language $L = \{0^n 1^{2n} \mid n ≥ 0\}$ as a context-free grammar? I am new to this field and I am not sure what should I do. Please help me.
1
vote
1answer
24 views

Point and Application of Recursive and Recursive Enumerable Languages

What is the point and application of recursive and recursive enumerable languages. Finite Automaton is used for pattern matching, designing computer architecture and protocols, CFG is used for ...
2
votes
2answers
37 views

How to graph search a LTL-generated Buchi automaton to generate valid execution paths

I have a set of tasks, and a LTL specification that describes which orders of the tasks are legal. I want to find a way to enumerate all permutations of the tasks that meet the specification. For ...
1
vote
1answer
25 views

why it said the “The left recursion has been removed at the cost of an extra non-terminal symbol(E1) and a little extra complexity”?

When I read the book "A Practical approach to compiler construction" the chapter 4 "approaches to syntax analysis" and the section 4.2.3.3 Left Recursion, it says: "The left recursion has been ...
0
votes
1answer
36 views

Different context-free grammars for the same language

In context-free grammar, are both the following grammars correct for the same language? $$L = \{a^mb^n : m, n \in N_0 \text{ and } m \ne n\}$$ (grammar one) $S \to S_1 | S_2$ $S_1 \to A_1B_1$ $...
4
votes
2answers
77 views

Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular

We know that $L=\{0^{m^2}\mid m\geq 3 \}$ is not a regular language. However $L^*$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can ...
1
vote
1answer
29 views

Number of strings accepted by this regular expression

This was a question that I got while taking a test at our university. The question paper was taken away after the exams. I remember the question only, not the multiple choices. If a regular ...
0
votes
1answer
45 views

Drawing a NFA for a string

I have these grammar rules defined as follows, FDL -> FDEF FDL | ε FDEF -> #feature #: FEXP FEXP -> #op #( FLIST #) FLIST -> FEXP #, FEXP | #feature ...
4
votes
2answers
2k views

if P=NP, why is P a subset of NPC?

Assuming P = NP, why should P be a subset of NPC? Here is how I understand it: P is a subset of NP NPC is a subset of NP if we solve an NP Complete problem on a deterministic machine in polynomial ...
4
votes
0answers
50 views

Why does Turing Tumble need gear bits to be turing complete?

I understand intuitively that gear bits in the massively successful Turing Tumble game (funded by kickstarter) are necessary for Turing completeness*. I had a fantasy about building a computer with ...
0
votes
1answer
48 views

DFA that accepts two more $1$'s than $0$'s

What is the state diagram of a DFA that follows $L = \{w \in \{0,1\}^*\mid w\text{ has at least two or more 1's than of 0's}\}$. Examples: $110$ doesn't work, $1110$ works.
1
vote
1answer
38 views

Difference between regular language and context free language

What is nature of difference of regular language and context free language? My guess is RL - CFL = RL CFL - RL = CFL Am I correct with this?
0
votes
0answers
28 views

Conversion from automaton to left linear grammar

I stumble across this problem: Give right linear grammar. The solution given was simple: $S\rightarrow bA$ $S\rightarrow aS$ $A\rightarrow \lambda$ $B\rightarrow bA$ $A\rightarrow aB$ Earlier ...
3
votes
1answer
150 views

Understanding application of Arden's theorem to find regular expression

I learnt Ardens theorem and its usage as follows: Ardens Theorem Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$ does not contain null string, then $R = Q + RP$ has a ...
1
vote
1answer
16 views

Can we call deterministic equivalent of all NFA to be finite

Finite automata is defined as a simple machine having small memory. A deterministic equivalent of a NFA with n states will have O(2^n) states,so the number of states grow exponentially. So can we ...
1
vote
0answers
37 views

Are LL(1) grammars a subset of LR(0) grammars?

As far as I've understood it seems that LL1 are a subset of LR0, but studying the following grammar I end up in a contraddiction. Grammar : S -> (S) | [S] | {S} | ε This is an LL1 while it seems ...
1
vote
1answer
39 views

Construct a pushdown automaton for $\{a^{2n}b^{3n}|n\ge0\}$

My idea is to (not formal) push an 'a' when we see an a, nondeterministically guess when n a's were seen from the input word, go to the next state. From there, when we see an a, push 2 'a's into the ...
1
vote
1answer
22 views

Probabilisitc timed automaton

I am kind of new to timed automaton domain. I am trying to understand in which way they are different to Markov Decision Process. First I know there objectives is to solve the non-determinism of a MDP....
0
votes
0answers
19 views

Number of non deterministic finite automata that can be constructed for $n$ states and alphabet with $m$ symbols

I came across the fact that The number of DFAs that can be constructed for $n$ number of states and alphabet containing $m$ symbols is $n\times (\color{red}{n}^m)^n \times 2^n$ So I was wondering ...
0
votes
1answer
11 views

Simple path in a Finite Acceptor

What is the definition of a 'simple path' in a finite acceptor? My concern is whether self loops can be considered as a part of simple path from initial to final state?
0
votes
0answers
31 views

Non deterministic turing machine vs Turing machine with stay option

According to book by Peter Linz, the transition function for non deterministic Turing machine is: $Q\times \Gamma\rightarrow 2^{Q\times \Gamma\times \{L,R\}}$ where, $Q$ is a set of ...
1
vote
1answer
40 views

How to Specify the Behavior of Automata for Verification

I am wondering what it takes to "verify" or "prove" that an automaton is correct. What the components are that are required. It seems that an automaton would be an easier thing to formally verify as ...
1
vote
1answer
75 views

Rectangular Automata

have a question regarding rectangular automata and their derivatives. In each location the derivates are defined by a interval, how are the derivates applied on the variables? Is one value chosen ...
1
vote
1answer
46 views

DFA for strings with number of 0's odd only in substring longer than 1

I'm trying to design and DFA that accept string with an odd number of 0`s, but counting only the ones within sub-strings with two or more 0. So, for example, 011000, will be accepted since it has 4 0`...
0
votes
0answers
56 views

Show that language is context-free

Let $A$ be a pushdown automata with input alphabet $\Sigma$ and stack alphabet $\Gamma$ and let $R \subseteq \Gamma^∗$ be a regular language. Let $L_R(A) \subseteq \Sigma^∗$ be a language of such ...
4
votes
2answers
94 views

Simplification of regular expression

I have some issue with how to simplify regular expression. I cannot find any suitable method to approach these types of problems. How would one approach simplifying the following regular expression: ...
1
vote
1answer
28 views

Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?

Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular. My proof: Let $M = (\Sigma, Q, \delta, q_0, F)$ be an ...
0
votes
1answer
37 views

Type-0 grammar and terminal symbols

The question is pretty short, but I've been thinking about it quite some time: Are terminal symbols that are not in the defined alphabet still valid?