Questions tagged [automata]
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.
1
vote
3answers
57 views
Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2
Given is an alphabet $\Sigma = \{ a, b, c \}$, and a language $A4 =\{ w \mid w \in \Sigma^* \wedge |w|_a \operatorname{mod} 2 \ge |w|_b \operatorname{mod} 2 \}$
whereas $|w|_a$ is the number $a$'s in ...
0
votes
1answer
19 views
How to generate a grammer from this language? [duplicate]
I'm trying to generate a grammar from this language:
L={a^i b^j c^k d^l : i+j=k+l}
to be clear its a in the power of i and b in the power of j... and so on, so ...
0
votes
1answer
51 views
Ambiguous grammar to equivalent unambiguous grammar
I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous.
Given the ambiguous CFG :
$S \to A\mid B$
$A \to aAb\mid ab$
$B \to abB\mid \epsilon$
My ...
1
vote
1answer
38 views
Constructing a pushdown automaton that accepts L*
Would appreciate if you could take a look at what I did and help me finish it.
Given a pushdown automaton that accepts a language $L$ by final state, construct a pushdown automaton that accepts $L^*...
1
vote
1answer
29 views
is $0^x1^y$ context-free?
given that L is regular, does the following make a context-free language?:
i) $\{0^x1^y \mid 0^{x+y} \in L\}$
ii) $\{0^x1^y \mid 0^{x-y} \in L\}$
since L is regular, i presumed that i) can be put ...
1
vote
1answer
29 views
Intersection of two incomplete DFAs
Let assume that I have the following two automata A1 and A2 :
I have to do the intersection of the two, so I did this :
My question is related to the "∅". If I have two incomplete automata without ...
0
votes
0answers
10 views
Push Down Automata [closed]
What is the purpose of stack in Push down Automata, does it has to do something with the word count of a language or just to push and pop the words of a language?
0
votes
0answers
18 views
What is abstract machine for parallel multiple context free grammar (PMCFG)?
It is said, that PMCFG (Parallel multiple context free grammar) http://www.aclweb.org/anthology/P93-1018 is mildly context-sensitive grammar. My question is - what abstract machine can be used for ...
0
votes
0answers
20 views
How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]
I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
0
votes
1answer
33 views
Regular expression or automata for language with odd number of 0's and odd number of 1's
Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
0
votes
1answer
32 views
What is the set of languages accepted by empty stack pda?
I am having a confusion. Empty stack pda will always accept episilon. Therefore a language not accepting episilon will still be accept episilon, so how can we avoid this?
1
vote
1answer
30 views
finding separating words (Nerode)
i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me ...
5
votes
2answers
220 views
Constructive proof to show the quotient of two regular languages is regular
I have a question regarding the quotient of two regular languages, $R$ and $L$.
I saw the answers to this question: are regular languages closed under division
and the proof sketch is not ...
2
votes
2answers
53 views
How to prove certain parts of one regular language restricted by another regular language is also regular?
I’ve encountered the following difficult question that I don’t know how to solve.
$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...
0
votes
0answers
38 views
How to design synchronisation algorithm to combine two automata?
I have two automata of states, transition and events (Etat, Transition, evenements) and I want to create a function that create the synchronized product between those two automata. For instance, given ...
0
votes
1answer
28 views
Nondeterministic automaton accepting only words whose first letter is identical to their next to last letter
I was asked this question and could not come to the correct answer:
Let $L$ be the language of all words over $\{a,b\}$ where the first letter is identical to the letter that is next to last. (Pay ...
0
votes
1answer
39 views
Which one of the following string is DCFL
Is odd length pallindrome DCFL or NCFL?
Like
1) $L=\{w1w^R\mid w \in \{0, 1\}^*\}$
or
2) $S\rightarrow aSa\mid bSb\mid a$
or
Suppose odd length String like
3)$S\rightarrow aSa\mid bSb\mid aSb\...
-1
votes
3answers
62 views
why can not NPDA is equal to DPDA?
I have recently read that turing machine can be remodeled to perform as PDA now, i have a question that since DTM = NDTM ( non deterministic Turing machine) then every DTM can remodeled to be NDTM ...
0
votes
0answers
20 views
Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#…#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]
Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
0
votes
0answers
13 views
contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2} [duplicate]
Is this language contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2}. I think it's not but can't prove it.
0
votes
1answer
38 views
What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?
I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking ...
5
votes
2answers
133 views
Why do DFAs with a single final state have less power?
I came across this question in a test and I had to answer whether it is true or false.
DFA with single final state has the same powers as DFA with more than one final state.
I was confused by what ...
2
votes
2answers
71 views
Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L
I'm having trouble with proving the following, and my attempt and confusion is mentioned further below.
PROBLEM STATEMENT:
For a string $w = a_1 a_2 a_3 a_4 a_5 a_6 a_7 \dots$, define $third(w) = ...
4
votes
1answer
52 views
Does the following operation makes the language regular? [duplicate]
I came across a question stated as $L = \{wxwy \mid w \in \{0,1\}^* , x,y \in\{ 0,1\}^* \}$ is regular and I have no problem understanding it.
However I thought what could happen if the language is ...
0
votes
1answer
22 views
Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.
...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM.
I had this problem on my exam. From my ...
0
votes
1answer
20 views
Counterexample for simple parity automaton reduction
I am dealing with deterministic parity automata and state space reduction (not minimization).
If we define $\equiv_L$ to be the equivalence relation that sets two states equal iff starting from those ...
1
vote
1answer
22 views
is it possible to know if a language is regular if its equivalence classes are finite?
i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.
1)suppose we have some language L over $\Sigma$, can we know if L is regular ...
2
votes
1answer
36 views
Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language
For regular languages $A,B\subseteq\{0,1\}^*$, is
$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$
regular, where $|x|_1$ means the number of appearances of 1 in the word $x$?
i need to ...
0
votes
1answer
36 views
Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$
I am looking for an unrestricted grammar which generates the following language:
$\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$
That is, words like $a\#aa\#aaa\#aaaa\# \dots \# \text{$k$ times '$a$...
1
vote
1answer
28 views
DFA that accepts strings with last character being repeated at least 1 time before
I'm trying to design a DFA in a 4 digit language, for example L(a,b,c,d) or L(1,2,3,4) that accepts strings with the last character being already repeated before.
Everyway im trying, i get so many ...
0
votes
1answer
77 views
Is this concatenation of two FA done right?
$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$
Details:
Consider ...
-1
votes
1answer
25 views
Is it possible to create a regular language from an non regular language? (details inside)
I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it?
say L is irregular, if we add or remove finite number of ...
2
votes
2answers
309 views
Language of all strings that has exactly 1 triple b
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.
Suppose we have a language L, Language of all strings that has exactly 1 triple “b” ...
1
vote
1answer
18 views
Number of states in DFA equivalent to given NFA
Let's say there is a NFA with $n$ states with an alphabet consisting of $x$ symbols. I convert it to an equivalent DFA. Can I say that the number of states in the equivalent DFA is $x^n$?
1
vote
1answer
27 views
Determining initial and final states from FA diagram
I am new to automata. And learning to find concatenation of two FAs. But this one has confused me
I know how to do concatenation but I am confused that in FA 1, what does x1 means? Is it mean final ...
1
vote
1answer
25 views
Trouble understanding this proof about the minimum number of states of a deterministic finite automaton
So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding ...
0
votes
1answer
25 views
Transition diagram for following token number
number -> digits(.digits)?(E[+ -]?digits)?
This transition diagram runs the above mentioned token I can not understand this how this is work.what is meaning of "?"Symbol and digits. can anyone ...
0
votes
1answer
36 views
LR parsers and ambiguous and non deterministic grammars
Dragon book says:
An ambiguous grammar can never be LR.
And then immediately further it says:
For example, consider the dangling-else grammar:
$\begin{align} stmt \rightarrow & \textbf{...
1
vote
1answer
15 views
Automaton without variables and guards for queueing system
Disclaimer: Assignment question.
I am trying to solve the below question, the condition is not to use guards and variables. Is it at all possible to do this?
My approach was to have 4 separate ...
0
votes
1answer
81 views
How can I make automaton that has given language? [closed]
I am trying to solve above question, below is the automaton I came up with:
Is there any ways to define automaton without having marked states?
2
votes
1answer
58 views
Name for the tree formed after collapsing cycles
What do you call a structure which becomes a tree after collapsing cycles (so the new vertices are the old faces)?
For instance, the digraph (given by an NFA; ignore edge labels please) below becomes ...
1
vote
1answer
26 views
In which environment we use NFA(Non Deterministic Finite Automata)?
We have two types of Automata. One is NFA and second is DFA. These are little bit different but thing is that in which environment we prefer NFA over the DFA?
1
vote
0answers
15 views
Clear definitions of various terms related to top down parsers and classification of the same
I am trying to clearly define various terms related to top down parser "so that I can relate them and come up with clear classification". Now this efforts might seem unnecessary as the terms I am ...
-1
votes
0answers
26 views
First part of L=L(A) proof (L(A)⊆L) proves that “δ̂(p,w)=p⇒w has even number of 1s,” so does second part (L⊆L(A))'s use depend on first part's use?
For this proof problem ( https://www.docdroid.net/IcdzSBt/theproblemanditssolution.pdf ), which includes its solution, does the "δ̂(p, w) = p ⇒ w has even number of 1's" from the second part (L ⊆ L(A))...
1
vote
2answers
47 views
What to do with empty set during NFA to DFA conversion?
I am currently converting this NFA to a DFA
I have come up with the following DFA:
...
5
votes
3answers
201 views
DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$
Construct a DFA $M$ with $\Sigma = \{a\}$ and max. 11 states so that $a^{23}\not\in L(M)$ but $\{a^i|i\geq 24\}\subset L(M)$.
I don't see how it is possible? Because it's a DFA and the alphabet only ...
0
votes
0answers
16 views
Example of a language with linear NFA, but exponential DFA [duplicate]
So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
1
vote
1answer
81 views
Context Free Grammer and PDA (Palindrome but without characters repeating in a row)
So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says
"L contains palindromes that don’t ever have the same character occur twice ...
3
votes
1answer
50 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
35 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 ...
