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

learn more… | top users | synonyms

1
vote
1answer
78 views

Regular expression arithmetics

What are the rules of regular expression arithmetics ? For example: Let $\Sigma=\{0,1\}$ $1. 1+01=(\epsilon+0)1$. $2. (\epsilon+00)^*=(00)^*$
1
vote
1answer
221 views

Random cellular automaton with three colors.

Does exist a Cellular Automata Rule that is RANDOM (like rule 30) and has 3 colors? I mean, as Wolfram says in his book, rule 30 shows a random behavior with some limits. But this happens using 2 ...
1
vote
1answer
1k views

Nondeterministic PDA to Deterministic PDA

Are there any resources on how to convert a non-deterministic PDA to a deterministic one, if a deterministic PDA actually exists? Or is there a step by step way on how to do this, kind of like going ...
1
vote
1answer
120 views

What is this operation between sets {a, b}{c, d} do?

Not sure what this operation does, which is why i'm on here. It's not the cartesian product and no idea what it's called. I need to know to prove: For any language L, (Null set)L = L(null set) = ...
1
vote
1answer
1k views

Proving regular expressions to be equivalent

I'm trying to prove that two regular expressions are equivalent. I mean prove in the rigorous sense of the word (i.e. this is a legit proof). The process is to show that R1 is a subset of R2, and ...
1
vote
1answer
25 views

Construct a deterministic finite state automaton

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10. This is what I drew. Not sure if its correct. State 2 is the final state. Am I missing ...
1
vote
1answer
27 views

Let $LOOP_{TM}$ be descriptor language of all touring machines that won't halt for any input. Show reduction of $HALT_{TM}$ to $LOOP_{TM}$

Question from Homework that I'm having difficult to answer on: Let $LOOP_{TM} = \{\langle M\rangle \mid \text{M is a TM that does not halt on any input w}\}$ Let $LOOP_{TM}$ be descriptor ...
1
vote
1answer
27 views

Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
1
vote
0answers
42 views

Where is my mistake in this DFA minimization?

I'm currently having trouble minimizing my DFA. I have the following graph: (ignore the numbers after ":") Using the table minimization method I reached: (x is distinguishable, O is ...
1
vote
0answers
59 views

Show that language $L'$ is regular given $L$ is regular

I show you some solution and I ask you for looking at it. $L'=\{y|\exists_{z,x} xyz\in L\wedge |x|=|y|=|z|\}$ Automaton for language $L$: $M=(Q,\Sigma, \delta, q_0, F)$ For language $L':$ $M'=(Q', ...
1
vote
0answers
128 views

nth-root of continued fraction with Raney transducers

There are some algorithms for doing basic arithmetic by using regular continued fraction expansions. These algorithms are mainly due to Gosper (1972) and Raney (1973). These two approaches use ...
1
vote
1answer
36 views

Is the empty set/language contained in the following set

Assume I have the following set of languages: $$ \{L \subseteq \{0,1\}^* \mid \text{for all $w \in L$, $|w| \leqslant 3$}\} $$ I know it contains the language containing the empty word since the ...
1
vote
2answers
31 views

Algorith/ Equation to get the ith element in N x N

I am having a difficulty figuring out the equation to get the ith element in $\mathbb{N}\times \mathbb{N}$ ( crossing the set of natural numbers).We have $\mathbb{N}\times \mathbb{N} = \{ ...
1
vote
1answer
54 views

Prove that $\{ww^R\#ww^R\}$ is not context free

I need to prove that $L = \{ww^R\#ww^R \; | \; w \text{ is in } \{a,b\}^*\}$ is not context free. I have tried using the pumping lemma for this. For $w=a^pb^pb^pa^p\#a^pb^pb^pa^p$. I have two cases ...
1
vote
0answers
29 views

question about determinstic pushdown automata

i need to show that there is no DPDA accepts the language $L=\{a^n*b^n \mid n>0\}\cup\{a^n*b^{2n} \mid n>0\}.$ i used the prefix property but i'm stuck showing that if $w,w' \in L$, $w$ is ...
1
vote
1answer
91 views

Prove that $L=\{a^nb^nc^md^m \mid m,n >=0\}$ is context free language

I'm trying to write the grammar of this language, in order to prove that it is CFL but I'm stuck because m or n could be 0. The language is: $L=\{a^nb^nc^md^m \mid m,n >=0\}$ . If they were ...
1
vote
0answers
55 views

What is the highest state in the context of finite state automata?

I am doing an assignment for my Theory of Computation course. We are writing a function and I am having a hard time understanding what "highest" state means in the following context: ...
1
vote
0answers
133 views

Help with proving a language is regular (Sipser problem 1.49a)

I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated. This question is ...
1
vote
0answers
61 views

Pumping Lemma for Context Free Languages: Is this language CFL?

I am learning for the first time the Pumping Lemma for CFL, and I thought I understood how it works until I came across this example: "Show that $L = \{a^m b^m c^n \mid m \leq n\}$ is not a CFL." My ...
1
vote
1answer
56 views

How to prove that a language `L` is not a regular language?

Given the following question: Prove that the following language is not a regular language: A language L in alphabet $\Sigma = \{a, b\}$ where every word ...
1
vote
0answers
23 views

how to create transition system/automata for modulo 4

I don't know how to think when to build a transition system/automata to calculate modulo 4 a of binary numbers. I know that the last two binary digits gives the rest but I need to go through hole ...
1
vote
0answers
44 views

Is this correct way to prove that { $uv$ $\mid$ $u$ and $v$ are strings over $(0,1)$ & $|u| = |v|$ } language is not regular?

I proved this using Pumping Lemma in the following way, Taking $p$ as pumping length then let us take a string $S$ where, $|u| = |v| = p$ Now according to pumping lemma $S$ can be split into three ...
1
vote
1answer
52 views

Constructing a NFA from a right linear grammar, is this correct?

Given the right linear grammar G S -> abA | bbB | a A -> bB | aA | b B -> baB | aaaA | [Epsilon/Terminates] Is the NFA in the image below the proper ...
1
vote
1answer
60 views

Difference between a*b and a*+b? Does the “+” denote Kleene plus or “or”?

Me and a friend are study for a quiz and are trying to determine the difference between the two NFA's produce by the regular exressions a*b and ...
1
vote
1answer
28 views

context free grammar that describes even numbers

I am learning about context-free grammars and as a toy example I wanted to design one that describes binary digits ending with 0. My attempt : S -> 1S | 0S | e0 - where e is the empty string. Is this ...
1
vote
1answer
55 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
1
vote
1answer
194 views

Complex automata Rubiks cube question (with picture) help needed

Question 1 A Rubik’s Cube is a puzzle in the shape of a cube. Each face is covered by nine stickers, each of which is coloured with one of six colours: white, red, blue, orange, green, andyellow. An ...
1
vote
2answers
635 views

pumping lemma: ww^R not regular

I'm trying to prove that $L = \{ww^R : w \in \{a,b\}^*\}$ ($w^R$ is the reverse of $w$) is not regular using the pumping lemma. Let $p$ be the pumping length and $s = a^pbba^p$. $x = \epsilon$, $y = ...
1
vote
0answers
67 views

Create a finite-state machine

I need to create a finite-state machine which accepts strings whose characters are in {a,b,c} and produce output strings of T's and F's. The machine outputs a T once the characters ab is encountered ...
1
vote
0answers
96 views

Proving context free language membership is $P$ complete with respect to log-space reductions

This is exercise from Introduction to Automata theory, Languages and Computation, by Hopcrof, Ullman (first edition). I found example of polynomial reduction to some problems in logic, or graph ...
1
vote
2answers
60 views

How to construct NFAs that recognize the following languages.

I am new to this computation theory and I am trying to answer the following question. Can you please check if I am on the right track? If there is any material that I can study for problems like ...
1
vote
2answers
104 views

Formal Languages - Regular Expression

I've been battling the following two questions for more than a day today. Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb. Write a regular ...
1
vote
1answer
44 views

Can someone explain me the proof?

I don't really understand the proof and I don't understand why it is M2 that "leads" to a reject state instead of M1.
1
vote
0answers
62 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
1
vote
1answer
549 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
1
vote
2answers
72 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
1
vote
0answers
25 views

Can the NFA constructs be minimized?

When converting a regular expression to a NFA you need to use certain constructs. My question is can these constructs be minimized? We have one with 4 states, I want to use the one with 2 states ...
1
vote
2answers
566 views

How do we prove that a particular DFA is minimal?

I guess we need to prove that there is no redundant state, so can we use state elimination and prove that the regular language is minimal? We could prove that the regular language is minimal by ...
1
vote
0answers
55 views

Theory of Automata concepts

I just started taking Theory of Automata and I'm having a hard time understanding some of the concepts. It's been only a week and the following questions are my homework. I'm not asking you to do my ...
1
vote
1answer
39 views

Languages that are not comparable in $R$

I want to know if there are $2$ languages $A,B\in{R}$ such that there's no reduction between them. Namely, $2$ languages $A$ and $B$ $\in$ $R$ such that $A\not\le B$ and $B\not\le A$ Thanks a lot!
1
vote
0answers
59 views

Extended PDA vs TM

We studied in class that PDA is less powerful than TM. My question is: Extended PDA : for every $\alpha,\beta \in \Gamma \cup \{\epsilon\}$, $\sigma \in \Sigma \cup \{\epsilon\}$, $q,r \in Q$, $w ...
1
vote
0answers
48 views

Language requiring a DFA with a certain number of states to implement

For any function $f\colon\{0,1\}^n\to\{0,1\}$, define a language $S_f = \{(b_1,b_2,\ldots ,b_n)\in\{0,1\}^n : f(b_1,b_2,\ldots ,b_n) = 1\}$. So all words in the langugage has same length $n$. I have ...
1
vote
1answer
239 views

DFA for Boolean Formula

Let $ f\left( b_{1}, \dots , b_{n} \right)$ be a boolean function. Define $S_{f} = \{\left( b_{1}, \dots , b_{n} \right): f\left( b_{1}, \dots , b_{n} \right)=1; b_{i} \in \{0,1\}, 1\leq i \leq n \}$ ...
1
vote
0answers
99 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
1
vote
1answer
71 views

One counter automata

A one-counter automaton $M = (Q, S, \Gamma, t, s, A)$ is a pushdown automaton where the stack alphabet $\Gamma$ contains just two symbols $\#$ and $g$. The symbol $\#$ is initially written on the ...
1
vote
0answers
52 views

$DFA/NFA$ for $L(OPPOSITE)=\{uv:vu\in L\}$

I'm trying to prove that: $L(OPPOSITE)=\{uv:vu\in L\} \in L_{FA}$ given that: $L \in L_{FA}$ . I'm trying to construct a finite automata that accepts $L(OPPOSITE)$ in order to prove it but I got ...
1
vote
1answer
62 views

Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
1
vote
0answers
113 views

Constructing an NFA accepted by a grammar

Contruct an NFA of the language accepted by the grammar below. $$G=(\{S,A,B\}, \{a,b,c\},S,P)$$ $P: S\rightarrow abaS\ \ | \ cA\\ \ \ \ \ \ \ A\rightarrow bA\ \ | \ cB \ \ | \ aa\\ \ \ \ \ \ ...
1
vote
2answers
102 views

Finite automata and languages question

I have attempted these few simple questions, can someone let me know if this is correct please? If not please provide the answer as I learn better that way and if possible explain. i) FA1 Start = ...
1
vote
0answers
23 views

Given two minimal FSMs with one accepting a subset of the other, must a simulation exist?

As part of an example, Abstract and Concrete Categories, section 3.35, claims: For every two minimal [by number of states] $\Sigma$-acceptors $A$ and $A'$, there exists at most one simulation $A ...