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?
