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 tagged [automata]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

0
votes
0answers
7 views

Concatenation of transition System

I don't understand how can I make the concatenation of transition System with P safe ( in question c ). In the first question (a) why I have as feedback c^not a from the third state to second state, ...
-4
votes
0answers
12 views

Concatenation of transition System and nfa [on hold]

I don't understand how can I make the concatenation of transition System and NFA. I read the book of ( principles of modelling) but I didn't find a practical way to make it. I appreciate that If ...
0
votes
1answer
42 views

Convert this grammar to language

I want to convert the following grammar to language but I am not able to think and answer. $$S \to aSa \mid bSa \mid ab \mid ba$$ It gives me a lot of choices when I tried building its derivation ...
0
votes
1answer
29 views

building a DFA from equivalence classes of $R_L$(tricky)

i've encoutered an interesting question from an old exam with no solution and i was wondering: how do you build a dfa(deterministic finite automata) from given equivalence classes? this is the ...
0
votes
0answers
22 views

finding equivalence classes of $R_L$ in automata(Nerode)

i am having trouble understanding this concept. would really appreciate your corrections so i could learn and improve. 1)$L=\left\{w\:\in \Sigma^* |\:w\:begins\:and\:ends\:with\:aa\right\}$ 2)$L=\...
0
votes
1answer
53 views

which of the following languages over $\Sigma \{0,1,\$\}$ are regular?

i saw this nice exercise in some old summary and i was wondering if i got it correctly. basically i have to decide whether a language is regular or not and give a short explanation. (languages over $\...
0
votes
1answer
32 views

proving that $a^6 \in L$ (tricky) (pumping lemma)

i've encountered a quite tricky question that i don't understand, and would appreciate your help with: it is said that by the pumping lemma, for a certain L there exists(guarenteed) n=2. also known ...
0
votes
0answers
21 views

NFA to Regular expression

Above is a try of converting a NFA to a regular expression (can a moderator rotate it please). There must be somewhere along the process where I do something wrong because if you compare the end ...
0
votes
0answers
7 views

When does the initial state lead to empty string when converting a DFA to context-free grammar?

I saw several examples of converting DFA to context-free grammar. Sometimes the grammar output includes the production rule such that the initial state $S$ leads to empty string: $S\to\epsilon$, ...
1
vote
1answer
32 views

How can I prove given language is not regular?

My first post here, so glad I found this great place. Hoping I could improve and learn a lot from you and contribute in the future if I can. I have a problem with the following scenario: Given $\...
4
votes
0answers
157 views

How many Nerode equivalence classes does the language $x\neq y$ have?

I have a language $L_k$ over the alphabet $\Sigma=\{0,1,\#\}$ defined as follows: \begin{equation} L_k=\{x\#y|x\in\{0,1\}^k,y\in \{0,1\}^*\wedge x\neq y\} \end{equation} I would like to find all the ...
5
votes
1answer
31 views

Regular Expression From a DFA

I am trying to create a finite automate that would accept any strings that have at least to 0s but reject all strings that have consecutive 0s. I have designed a DFA for this purpose but am having ...
0
votes
1answer
51 views

Given a regular language L, prove or disprove L' is regular

Given $NFA$ $N$ , $L(N)$ regular language and two words $w1$,$w2$ $\in$ $\sum^*$ such that $w1$ $\neq$ $w2$. I have to prove or disprove that $L'=$ {$z\in \sum^*|\exists$ $w1,w2$ :$w1z$ $\in$ $L(N)$ ...
0
votes
0answers
14 views

build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

I think it's similiar to NFAs. I replace the finite states of the given automaton for start-states for my new automaton. I do it with $\epsilon$-transition from the start state to the actual finite ...
-1
votes
0answers
281 views

Automata theory - How many Nerode equivalent classes for language $L_k$ [duplicate]

Given a constant $k$ we will define the language: $$L_k =\{x\#y \mid x \in \{0,1\}^k, y \in \{0,1\}^* \text{ and } x \not=y\}$$ How many Nerode equivalent class does $L_k$ have? I need to show ...
0
votes
1answer
31 views

Left Linear Grammer to Right Linear Grammer

I am learning Regular Grammar and given the problem to convert S->S10/0 from left linear to right linear grammar. I've seen examples of such conversions where we first write the reverse ...
2
votes
1answer
33 views

Proof for minimum number of states for a epsilon free NFA is $2^n$

I have the following question which I could not proceed: Let $$L=\{w \in \Sigma^* \mid \text{all symbols of the alphabet occur even times in } w\}. $$ Prove that any NFA accepting $L$ requires $2^...
0
votes
0answers
17 views

Conversion CFG to PDA

Given the following CFG: S → ASB A → aAS | a |ε B → SbS | A | bb I've got to convert it to a PDA by empty stack and to a PDA by final state. I've done it by final state and got the PDA: https://i....
0
votes
1answer
35 views

Conversion of an Epsilon NFA to a DFA

I need to convert this NFA to a DFA, but I only have the method for NFAs without Epsilons: My calculation was: But the expected result is: Is there a process to use for converting this to get the ...
3
votes
2answers
183 views

prove or disprove if the following language is regular language

for $A,B\subseteq\{0,1\}^*$ regular languages prove or disprove that $L_2$ is a regular language: $L_2 = \{x \in A | \exists y \in B : |x|_1 =|y|_1 \}$ $|x|_1$ means the number of appearances of 1 ...
0
votes
1answer
21 views

How to connect DFA state which had no transitions after minimizing it?

I have the following DFA, let it be $A$: The problem asks to find the minimal connected DFA for $A$, it is as follows according to the solution (the state $\{d,e\}$ is called $e$ for simplicity's ...
1
vote
1answer
20 views

How to find a DFA for combinations of even and odd occurrences $0,1$?

Let $L$ be a language over $\{0,1\}$ whose Nerode equivalence classes are: $$ \{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=0\}\\ \{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=1\}\\ \{w|\#_0(w)\...
0
votes
1answer
30 views

How to find equivalence classes for $R_L$ for the language of words that begin and end with $aa$?

Let $R_L$ be a relation such that: $xR_Ly \iff \forall z\in \sum^*:xz\in L \iff yz \in L$. Find the equivalence classes for $R_L$ for this language: $$ L=\bigg\{w\in \sum^*\bigg| w\quad \text{starts ...
1
vote
1answer
44 views

PDA: Symbol in first half

How do I construct a PDA where: $L = \{w \in \{0, 1\} ∗ : |w| \text{ is even and } w \text{ contains at least one 1-Symbol in the first Half}\}$ To me it seems impossible to know when I reached the ...
1
vote
1answer
32 views

'$L$ almost' is regular

Given a regular language $L$, I have to prove that '$L$ almost' is regular where '$L$ almost' is all the words which differ from the words of $L$ by one char. for example, if $L = \{aab,aaa\}$, so $...
1
vote
1answer
24 views

Are these languages regular?

$L_1 = \{0^k1^n \mid k \equiv n \bmod 3 \}$ This one I assume isn't since it's infinite $L_2 = \{0^k1^{3k+2} \mid k>0 \}$ This one I assume also isn't regular because it relates on $k$ on both $...
2
votes
1answer
38 views

Does my solution show that the language is uncomputable by applying rice's theorem?

If p is a Turing machine then L(p) = {x | p(x) = yes}. Let A = {p | p is a Turing machine and L(p) is a finite set}. Is A computable? Justify your answer. So I'...
1
vote
1answer
30 views

Finding a set that isn't in the image

$A_{DFA}(n)=\{M |M $ is a DFA, and $ |Q|=n\}$ , Where Q is the number of states in M. Therefore $\bigcup_{n =0}^\infty A_{DFA}(n) \\$ is the set of all deterministic finite automatons. Let $f:\...
1
vote
1answer
23 views

Let $L_4$ be the language over alphabet $\{0, 1\}$ defined by $L_3 = \{x : \#_1(x) = 2 \cdot \#_{10}(x)\}$ design for a PDA that accepts $L_4$

Let $L_4$ be the language over alphabet $\{0, 1\}$ defined by $L_4 = \{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 $\...
2
votes
1answer
43 views

DFA Minimization: Finding all Nerode equivalence classes.

So I read that you can easily read off the Nerode equivalence classes if you have a minimal DFA. So after the minimization process I got this: But how can I read off the equivalence classes? I read ...
1
vote
2answers
46 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 ...
0
votes
1answer
62 views

Binary prime numbers: grammar

I want to write a grammar which produces binary prime numbers. But I can't find any patterns this grammar can be made of. Like this: ...
0
votes
1answer
12 views

How to determine the beginning of $uv^iw$ in the pumping lemma for regular languages?

Let $\sum=\{a,b,c,d\}$, $L=\{a^ib^jcd^k \big| i\ge0; k>j>0\}$. Prove that $L$ is not regular using pumping lemma. We can choose the word $Z=a^0b^{n}cd^{n+1}=b^{n}cd^{n+1}\in L$. Let $uvw$ be ...
0
votes
0answers
28 views

How to prove that if $L$ is a regular language then $L'$ which is composed of words in $L$ with substrings as also words in $L$ is regular as well?

Let $L$ be a regular language. Let $L'=\{\sigma_1...\sigma_n|n\ge 1, \forall 1\le i\le n, \sigma \in \sum. \exists i: 1\le i\le n \quad\land\quad \exists u\in L: \sigma_1...\sigma_{i-1}u\sigma_{...
0
votes
1answer
21 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)?
0
votes
1answer
19 views

Drawing a dfsa where L is a set of strings that contains at most 4 zeros

For each of the following languages over alphabet $Σ = \{0, 1\}$, construct a DFSA that accepts it and a regular expression that denotes it. Prove that your automata and regular expressions are ...
0
votes
1answer
34 views

Inductive Proof With Regular Expression

I'm trying to prove that the elements of the language $L((01+10)(01+10)^*)$ have an equal number of $0$'s and $1$'s. So far I've the base case: $R^n \to R^0 = 01 + 10$, all of which have equal number ...
0
votes
1answer
45 views

How to find errors in the definition of DFA which expands upon another DFA?

Let $A=(\{0,1,2\}, Q,q_0,F,\delta)$. $A$ is deterministic finite automaton (DFA). We want to build a new DFA, $B$ off $A$ which would receive $L(A)\cap\{0,1\}^+$ as follows: $$ B=(\{0,1,2\}, Q\cup\{...
1
vote
1answer
30 views

How to use product automaton and intermediate state to prove existence of regular language?

Let $L$ be a regular language over alphabet $\Sigma$. Let $\frac{1}{2}L$ be the following language: $\{w\in\Sigma^* \mid \exists y\in \Sigma^*: |y|=|w|, wy\in L \}$. For example if $L=\{\epsilon, ...
0
votes
1answer
18 views

How to characterize a regular language for which exists a DFA which has a single accepting state?

This question is based off An example of non-empty regular language for which a DFA with single accepting state doesn't exist. Let $C$-type language be a regular language iff exists a ...
2
votes
1answer
42 views

Design a finite automaton that recognizes a word that begins with $a$ and even number of $b$

Given the language $$L=\{w\in\{a,b\}^*\mid\text{$w$ starts with $a$ and has a total of even $b$}\}$$ design a finite automaton that recognizes it. Consider $M=\bigl(\{q_0,q_1\},\{0,1\},\delta,q_0\...
1
vote
1answer
24 views

Is empty language a singly capacitated regular language?

A singly capacitated regular language is such that exists a deterministic finite automaton (DFA) which has a single accepting state. For example an empty language (whose alphabet is an empty set) is ...
0
votes
1answer
20 views

An example of non-empty regular language for which a DFA with single accepting state doesn't exist

Let $C$-type language be a regular language iff exists a deterministic finite automaton (DFA) $A$ which has a single accepting state such that $L=L(A)$. An example of a regular non-empty language ...
1
vote
1answer
43 views

Proving equality of two regular languages using operations closed under regular languages

Is there any way to prove that two regular languages A and B are equal using only closed operations under regular languages? (The languages can be expressed as regular expressions,NFAs, eNFAs or DFAs)...
1
vote
1answer
31 views

Give DFA accepting the following languages

over the alphabet {0,1} a) L = { w $\in$ {0,1}$^*$ | |w|$_{0} \leq$ 2 } b) L = { w $\in$ {0,1}$^*$ | w ends with 0} over the alphabet {a,b,c} L = { w $\in$ {a,b,c}$^*$ | |w|$_{ab}$ = 0 mod 2 and |...
1
vote
0answers
14 views

How to build deterministic finite automaton for words where $b$ (if exists) is followed by at least 2 occurrences of $a$?

Given the alphabet $\sum=\{a,b\}$ in any word that belongs to the language the character $b$ (if it exists in the word) is followed by at least two occurrences of $a$. For example, the string $a$ and $...
1
vote
1answer
41 views

finding the cardinality of a set , reversed languages

I'm trying to calculate the cardinality of $A$: $$A=\{L \subseteq \text{$Σ^*$}| \text{$L^R$}=L \}$$ Where Σ is a finite alphabet . The hint in my book says to use "Binary Representation of real ...
0
votes
0answers
26 views

DFA conversion to Regular Expression using state elimination

I'm trying to convert my DFA (accepts any string not containing 00) to regular expression using state elimination but I'm a bit lost as to the whole thought process. My DFA: My regular expression: ...
1
vote
1answer
31 views

How to draw a DFA from regular expression a*b*?

I'm doing some exercises to the topic DFA and noticed, that most solutions I could find to a specific language do not look like my own solution to it and I'm kinda confused. The condition of the L is {...
0
votes
0answers
16 views

Show that an FSA is equivalent to another FSA with only one initial state

Let $M = (Q, I, T, \mathcal{E})$. Construct $M' = (Q', I', T', \mathcal{E}')$ where $Q' = Q \cup \{q_0\},$ $I'=\{q_0\},$ $\mathcal{E}' = \mathcal{E} \cup \{(q_0, a, q) \mid \exists q_{I} \in I, (...