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

learn more… | top users | synonyms

1
vote
1answer
11 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
49 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
19 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
50 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
51 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
15 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
33 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
29 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
0answers
40 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
2answers
26 views

Is a DFA a subset of NFA? Why?

After reading this previous question Difference between NFA and DFA, it's clearer to me their relationship/differences. Can one say that a DFA is a subset of a NFA where both recognize a/the same ...
1
vote
1answer
25 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
0answers
26 views

Lattice worms with nontrivial deaths

In Paterson's worms, a triangular lattice is used. A worm can move in 6 directions. As each node is hit, the worm follows an internal rule for which edge it will eat next based on the edges already ...
1
vote
1answer
52 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
145 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
251 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
48 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
66 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
53 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
82 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
42 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
50 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
275 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
0answers
59 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
23 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
372 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
2answers
55 views

Reduction between two languages and a common one

My question is as following : Let $A$ and $B$ be some languages, there exist a language $C$ such that $A\le C$ and $B\le C$, where "$\le$" means "reducible to", so $A\le C$ means there is a mapping ...
1
vote
0answers
48 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
38 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
48 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
44 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
207 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
93 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
60 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
56 views

Turing Machines

Suppose that $\Sigma$ is a finite set and that $L_1$, $L_2$ and $L_3$ are Turing acceptable subsets of $\Sigma^*$ that satisfy the following properties: $L_1 \cup L_2 \cup L_3 = \Sigma^*$; $L_1 \cap ...
1
vote
0answers
49 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
60 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
88 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
94 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
19 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 ...
1
vote
1answer
401 views

Proving Language accepted by DFA

I am stuck with a problem, as my proving skills aren't good(trying to improve). Prob: Given a State Table of DFA, decribe what language is accepted, and prove by induction it accepts that language, ...
1
vote
0answers
163 views

PDA state diagram with an inifinite languge but with no looping states

For class I'm supposed to create a PDA state diagram that is capable of generating an infinite language with no state q such that q is reachable from the start state, there is no cycle within the ...
1
vote
2answers
437 views

For the regular expression, (a* + b*) . (a.b)* , does the following automaton recognise the language it describes?

I constructed the automaton below using the assumption that the language described by the regular expression above only accepted the following strings: Empty, aabab, babab, aaaabab, bbbabab etc ...
1
vote
0answers
116 views

Mathematical formulation of 'Indra's net'

Quoting Wikipedia: "Imagine a multidimensional spider's web in the early morning covered with dew drops. And every dew drop contains the reflection of all the other dew drops. And, in each ...
1
vote
0answers
196 views

Confusion related to state equivalence of finite state machines

I have this confusion if there are two states of a machine p and q. Let x be an input string such that length of x = k, g be the output function and let g(p,x) and g(q,x) be the output when the input ...
1
vote
1answer
91 views

How to formally describe this Uppaal automata?

I have the following simple automata: What I'm looking for is a formal description of this based on the definition here $A=(\Sigma,\Gamma,S,s_0,\delta,\omega, F)$ How to declare all the ...
1
vote
2answers
572 views

NFA to DFA conversion, half the power set

Is there a way to tell when a NFA will use at least half the power set when converted to a DFA. I tried to create a few examples, but i just can't see a pattern that would say whether an NFA will use ...
0
votes
1answer
141 views

Difference between $(a|b)^\ast$ and $a^\ast b^\ast$?

What is the difference between $(a|b)^\ast$ and $a^\ast b^\ast$? Can you show more examples of Kleene star and patterns and explain a little bit? I've searched so many sites in Google, but it returns ...
0
votes
3answers
188 views

Word problem in a free group

Can the word problem in a free group be solved by a finite state automaton? I know it can be solved by a pushdown automaton.
0
votes
3answers
658 views

Are these languages context free or not?

$L_1=\{a^nb^mc^nd^m \mid m,n >0\}$ $L_2=\{a^nb^mc^md^n \mid m,n >0 \}$ $L_3=\{a^mb^n \mid m+n\text{ is a prime number}\}$ $L_4=\{a^mb^n \mid n=m^2\}$ $L_5=\big\{ww^R\#ww^R \mid w \in \{a,b\}^* ...
0
votes
2answers
143 views

Prove the language $\{a^k b^l : k \neq l \}$ is not regular

Prove that the following language is not regular: $$L=\{a^k b^l : k,l \ge0, k\ne l\}$$ The problem is that I should use "distinguished states" not the pumping lemma, which is usually used for such ...